题目概述

给出 $X,Y$ 和 $\{a_n\}$ ，问有多少 $(i,j)$ 存在 $v$ 满足 $(a_i,v)=X,[a_j,v]=Y$ 。

解题报告

来分析一波：$X|v,v|Y\Rightarrow X|Y$ ，所以 $Y$ 不是 $X$ 倍数就无解，然后由于是 $gcd$ 和 $lcm$ 所以考虑质因数分解(PR大法好)，令 $Y=p_1^{y_1}p_2^{y_2}\cdots p_k^{y_k},X=p_1^{x_1}p_2^{x_2}\cdots p_k^{x_k},a_i=p_1^{A_{i,1}}p_2^{A_{i,2}}\cdots p_k^{A_{i,k}},v=p_1^{V_1}p_2^{V_2}\cdots p_k^{V_k}$ ， 则 $X|a_i,a_j|Y$ 且 $min\{A_{i,k},V_k\}=x_k\land max\{A_{j,k},V_k\}=y_k$ ，分类讨论之后会发现只要 $x_k<y_k$ ，那么就必须有 $A_{i,k}=x_k\lor A_{j,k}=y_k$ ，如果 $x_k=y_k$ ，那么这一位就没有任何限制（F**k这里我竟然卡了半天）。

现在问题转化为了求满足 $X|a_i\land a_j|Y\land(\forall k,A_{i,k}=x_k\lor A_{j,k}=y_k\lor x_k=y_k)$ 的 $(i,j)$ 的个数。

由于 $x_k=y_k$ 是没有任何限制的，所以我们可以把这些位无视掉，然后我们观察那个限制，会发现这很像位运算啊……如果令 $Sx_{i,j}=[A_{i,j}>x_j],Sy_{i,j}=[A_{i,j}<y_j]$ ，那么就需要满足 $Sx_i\ and\ Sy_i=0$ 。

这好眼熟啊……上高维前缀和就行啦。

示例程序

#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
typedef long long LL;typedef long double DB;
const int maxn=200000,maxp=16,prime[]={2,3,5,7,11,13,17,19};

int n,P,num[2][maxp+5];LL A,B,p[(1<<maxp)+5];
int a[maxn+5],b[maxn+5],m,Y[1<<maxp];LL ans;

inline LL Mul(LL x,LL y,LL MOD) {return ((x*y-(LL)((DB)x/MOD*y)*MOD)%MOD+MOD)%MOD;}
inline LL Pow(LL w,LL b,LL MOD) {LL s=1;for (;b;b>>=1,w=Mul(w,w,MOD)) if (b&1) s=Mul(s,w,MOD);return s;}
inline bool MR(LL n){
    for (int i=0;i<8;i++) if (!(n%prime[i])) return n==prime[i];
    for (int t=1;t<=8;t++){
        LL x,s;int k=0;for (x=n-1;!(x&1);x>>=1) k++;x=Pow(rand()%(n-2)+2,x,n);if (x==1) continue;
        for (s=Mul(x,x,n);k;k--,x=s,s=Mul(x,x,n)) if (s==1) {if (x<n-1) return false;break;}if (s>1) return false;
    }return true;
}
#define Abs(x) ((x)<0?-(x):(x))
LL gcd(LL a,LL b) {return b?gcd(b,a%b):a;}
inline void AMOD(LL &x,LL tem,LL MOD) {if ((x+=tem)>=MOD) x-=MOD;}
inline LL FindD(LL n){
    LL x=rand()%(n-1)+1,y,r=rand()%(n-1)+1;
    for (int i=1,k=1;;i++){
        AMOD(x=Mul(x,x,n),r,n-1);x++;if (x==y) return -1;LL GCD=gcd(Abs(x-y),n);
        if (GCD>1) return GCD;if (i==k) y=x,k<<=1;
    }
}
void PR(LL n){
    if (n==1) return;if (MR(n)) {p[++P]=n;return;}
    LL D;while ((D=FindD(n))<0);PR(D);PR(n/D);
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%lld%lld",&n,&A,&B);if (B%A) return puts("0"),0;PR(B);sort(p+1,p+1+P);
    for (int t=P,i=(P=0,1),j;i<=t;i=j) {for (j=i+1;j<=t&&p[i]==p[j];j++);p[++P]=p[i];num[1][P]=j-i;}
    LL x=A;for (int i=1;i<=P;m+=num[0][i]<num[1][i],i++) while (!(x%p[i])) num[0][i]++,x/=p[i];
    for (int i=1;i<=n;i++){
        LL x;scanf("%lld",&x);
        if (!(x%A)){LL now=x;int s=0;
            for (int j=1,k=0;j<=P;j++,k=0)
                if (num[0][j]<num[1][j])
                    {while (!(now%p[j])) now/=p[j],k++;s=s<<1|(k>num[0][j]);}a[i]=s;
        } else a[i]=-1;
        if (!(B%x)){LL now=x;int s=0;
            for (int j=1,k=0;j<=P;j++,k=0)
                if (num[0][j]<num[1][j])
                    {while (!(now%p[j])) now/=p[j],k++;s=s<<1|(k<num[1][j]);}b[i]=s;
        } else b[i]=-1;
    }
    for (int i=1;i<=n;i++) if (~b[i]) Y[~b[i]&((1<<m)-1)]++;
    for (int i=0;i<m;i++) for (int j=0;j<(1<<m);j++) if (!(j>>i&1)) Y[j]+=Y[j|(1<<i)];
    for (int i=1;i<=n;i++) if (~a[i]) ans+=Y[a[i]];return printf("%lld\n",ans),0;
}