【Codeforces 1016G】Appropriate Team
Pollard Rho，状态压缩，子集和。
题目大意：
给定 $a_1,a_2,a_3,\ldots,a_n$ 和 $X,Y$。
问有多少有序数对 $(i,j)$，满足：
存在一个正整数 $v$，有 $\gcd(a_i,v)=X$，$\mathrm{lcm}(a_j,v)=Y$。
题解：
我们对每个质因子分别考虑。
考虑 $\gcd(a_i,v)=X$ 的情况。对于一个质因子 $p$，如果 $a_i$ 中有 $m$ 个，$v$ 中有 $n$ 个，$X$ 中有 $k$ 个，那么 $\gcd$ 中就应当有 $\min(m,n)$ 个，即 $k=\min(m,n)$。
那么有以下几种情况：
- $m\lt k$。这种情况无法满足条件。
- $m\gt k$。这种情况只有 $n=k$ 才能满足条件。
- $m=k$。这种情况只要 $n\geq k$ 就可以满足条件。
我们称满足条件 $3$ 的质因子为自由因子。
$\mathrm{lcm}$ 也是类似的定义有自由因子。
$10^{18}$ 里，不同质因子个数最多大概也就是十六七个，所以我们可以对每个 $a_i$，用二进制数来状压 $\gcd$ 和 $\mathrm{lcm}$ 的自由因子。
考虑 $\gcd$ 的自由因子和 $\mathrm{lcm}$ 的自由因子分别为 $x,y$ 的情况。
我们仍然对于每一位进行考虑。
不难发现，每一位必须满足以下条件之一，这对数才能产生 $1$ 的贡献：
- 在 $x$ 中或者 $y$ 中，这一位是自由因子。
- 在 $X$ 中和 $Y$ 中这个质因子的出现次数相等。
那么对于 $y$，我们可以先把 $X$ 中和 $Y$ 中这个质因子的出现次数相等的那些位钦定为自由因子，然后只需要当前的 $y’$ 来考虑条件 $1$ 即可。
我们发现，$x$ 和 $y’$ 能产生贡献，当且仅当 $x$ 的补集是 $y’$ 的子集。
我们用数组存 $\gcd$ 的每种不同的自由因子状态（的补集）的出现次数，然后对其做子集和变换。
然后对于一个 $y$ 的贡献就可以快速计算了。
至于分解质因数，我们只需要对 $Y$ 进行 pollard_rho 即可得出需要考虑的那些因数。$a$ 中其他的因数可以不用考虑。至于 $X$ 中如果出现了在 $Y$ 中不存在的质因子，那么答案就是 $0$。
时间复杂度 $O(\sqrt {\sqrt Y}+3^{17}+17n)$。
Code：
#include<vector>
#include<cstdio>
#include<algorithm>
#include<ctime>
using namespace std;
const int N=2e5+5;
typedef long long LL;
inline LL mul(LL a,LL b,const LL&md){
LL c=a*b-(LL)((long double)a*b/md+.5)*md;
return(c>>63&md)+c;
}
inline LL pow(LL a,LL b,const LL&md){
LL ret=1;for(a%=md;b;b>>=1,a=mul(a,a,md))if(b&1)ret=mul(ret,a,md);return ret;
}
namespace MR{
const int P[]={2,3,5,7,11,13,17,19,23,29,31,37};
bool check(int a,LL n){
LL x=n-1;int d=0;
while(!(x&1))x>>=1,++d;
for(x=pow(a,x,n);d--;){
const LL lst=x;x=mul(x,x,n);
if(x==1&&lst!=1&&lst!=n-1)return 0;
}
return x==1;
}
bool test(LL n){
if(n==1)return 0;
for(int i:P)if(n==i)return 1;
if(!(n&1))return 0;
for(int i:P)if(!check(i,n))return 0;
return 1;
}
}
vector<LL>v;
LL find(LL n,int c){
LL x=rand()%(n-1)+1,y=x,k=2,q=1,t=1;
for(;;k<<=1,y=x,q=1){
for(int i=1;i<=k;++i){
x=mul(x,x,n)+c-n;x+=x>>63&n;
q=mul(q,llabs(x-y),n);
if(!(i&127)){
t=std::__gcd(q,n);
if(t>1)return t;
}
t=std::__gcd(q,n);
if(t>1)return t;
}
}
}
void rho(LL n){
if(n==1)return;
if(MR::test(n))return v.push_back(n);
LL p=n;int c=19260817;
while(p==n)p=find(p,c--);
while(n%p==0)n/=p;
rho(p),rho(n);
}
int n;LL X,Y;
int fx[23],fy[23],fz[23];
LL cX[1<<18],cY[1<<18];
void get(LL x,int*f){
for(int i=0;i<v.size();++i)f[i]=0;
for(int i=0;i<v.size();++i)
while(x%v[i]==0)++f[i],x/=v[i];
}
int main(){
srand(time(0));
scanf("%d%lld%lld",&n,&X,&Y);
if(Y%X)return puts("0"),0;
rho(Y);
sort(v.begin(),v.end());
get(X,fx),get(Y,fy);
const int C=(1<<v.size())-1;
for(int i=1;i<=n;++i){
LL x;
scanf("%lld",&x);
get(x,fz);
if(x%X==0){
int zt=0;
for(int i=0;i<v.size();++i)if(fz[i]==fx[i])zt|=1<<i;
++cX[C^zt];
}
if(Y%x==0){
int zt=0;
for(int i=0;i<v.size();++i)if(fz[i]==fy[i])zt|=1<<i;
++cY[zt];
}
}
LL ans=0;
for(int i=C;i;--i)
for(int j=(i-1)&i;;j=(j-1)&i){cX[i]+=cX[j];if(!j)break;}
for(int i=0;i<=C;++i){
int zt=i;
for(int j=0;j<v.size();++j)if(fx[j]==fy[j])zt|=1<<j;
ans+=cY[i]*cX[zt];
}
printf("%lld",ans);
return 0;
}