【数学】Codeforces1016G Appropriate Team

分析：

其实如果把$a_i，x,y$的范围调小一点，这就是道不折不扣的水题了。。。

如果$y\%x!=0$那么一定无解。

对$x、y$唯一分解，再对$a_i$因数分解，分别考虑其作为gcd的一侧和作为lcm的一侧的答案。

因为哪怕是$10^{18}$、质因数种类也不会超过18个
当$a_i$为gcd时，首先必须满足$a_i\%x=0$，然后用一个二进制数表示每一个质因数的次数是否和x相同（相同为0，不相同为1），设这个二进制数为$p_i$。
当$a_i$为lcm时，首先必须满足$y\%a_i=0$，然后用一个二进制数表示每一个质因数的次数是否和y相同（相同为0，不相同为1），设这个二进制数为$q_i$

要求的答案无非就是$p_i\space and\space q_i==0$的方案数。

这些应该都比较基础。

然后重点就是如何快速地唯一分解一个在$10^{18}$范围的数。
显然普通的$O(\sqrt{n})$算法是不可取的。

当然可以用pollard rho算法水过去。

官方题解给了一个更巧妙的算法。

先把$10^6$范围内的质数分解掉，然后剩余的数(v)如果不为1，那么其只有3种情况：
$设p、q为不相同的质数$
$v=p、v=p*p、v=p*q$

显然，第二种可以直接判断，问题是第1种和第3种如何判定。

官方题解的方法非常巧妙，它将x与所有的$a_i、v、y$分别求一个gcd，若值不为1且不为v，则为p。

如果找不到这样的p，则可以把它看做是个质数（因为尽管这个数可能是两个质数相乘，但其他数都没有这两个质因数，所以就可以忽略了）

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#define SF scanf
#define PF printf
#define MAXN 300010
#define y1 chunhua
using namespace std;
typedef long long ll;
ll x,y;
ll a[MAXN];
vector<ll> fac,facn;
vector<int> facx,facy;
vector<pair<int,int> >facv;
vector<ll> check;
int n;
ll sum[MAXN];
ll gcd(ll x,ll y){if(y==0)return x;return gcd(y,x%y);  
}
void factorize(ll val){for(ll i=2;i<=val&&i<=1000000ll;i++)if(val%i==0){fac.push_back(i);while(val%i==0)val/=i;}if(val>1){ll q=(long long)(sqrt(val));if(q*q==val){fac.push_back(q);return ;    }for(int i=1;i<=n;i++)check.push_back(a[i]);check.push_back(x);check.push_back(y);ll g=val;for(int i=0;i<check.size();i++){g=gcd(val,check[i]);if(g!=1&&g!=val){if(g<val/g){fac.push_back(g);fac.push_back(val/g);}else{fac.push_back(val/g);fac.push_back(g);   }return ;}}fac.push_back(val);}
}
int main(){SF("%d%I64d%I64d",&n,&x,&y);for(int i=1;i<=n;i++)SF("%I64d",&a[i]);factorize(y);if(y%x){PF("0");return 0;   }for(int i=0;i<fac.size();i++)facv.push_back(make_pair(0,0));ll x1=x;ll y1=y;for(int i=0;i<fac.size();i++){int cnt=0;while(x1%fac[i]==0){x1/=fac[i];cnt++;  }facv[i].first=cnt;}for(int i=0;i<fac.size();i++){int cnt=0;while(y1%fac[i]==0){y1/=fac[i];cnt++;  }facv[i].second=cnt;}for(int i=0;i<fac.size();i++){if(facv[i].first!=facv[i].second){facn.push_back(fac[i]);facx.push_back(facv[i].first);facy.push_back(facv[i].second); }}for(int i=1;i<=n;i++){if(a[i]%x)continue;ll val=a[i];int mask=0;for(int j=0;j<facn.size();j++){int cnt=0;while(val%facn[j]==0){val/=facn[j];cnt++;  }mask+=((cnt>facx[j])<<j);}sum[mask]++;}for(int i=0;i<facn.size();i++)for(int mask=0;mask<(1<<facn.size());mask++)if(mask&(1<<i))sum[mask]+=sum[mask-(1<<i)];ll ans=0;for(int i=1;i<=n;i++){if(y%a[i])continue;ll val=a[i];int mask=0;for(int j=0;j<facn.size();j++){int cnt=0;while(val%facn[j]==0){val/=facn[j];cnt++;  }mask+=((cnt<facy[j])<<j);}ans+=sum[(1<<facn.size())-mask-1];}PF("%I64d",ans);
}