Educational Codeforces Round 48 (Rated for Div. 2)G. Appropriate Team

笛里谁知壮士心，沙头空照征人骨。这篇文章主要讲述Educational Codeforces Round 48 (Rated for Div. 2)G. Appropriate Team相关的知识，希望能为你提供帮助。
【Educational Codeforces Round 48 (Rated for Div. 2)G. Appropriate Team】题意:求满足条件的(i,j)对数:(gcd(v,a_i)=x,lcm(v,a_j)=y)
题解:(x|a_i,a_j|y),(x|y),考虑质因子p,假设a_i中p次数为a,x中次数为b,y为c,(a_j)为d; a> =b,c> =d.
假设a> b,c> d,那么由于(gcd(v,a_i)=x),v中p的次数为b,由于(lcm(v,a_j)=y),那么(max(b,d)==c),又c> d,所以b=c< a和x|y矛盾,所以此时ij不满足条件
其他情况同理,能证明当a> b,c> d不同时满足时,都能,满足条件,考虑y的质因子只有15个,二进制状压,表示1为a> b,0为a==b,那么当两个二进制数and起来为0时,ij对满足条件.
分解质因子用泼辣的肉,and用fwt或者sosdp都行

//#pragma GCC optimize(2) //#pragma GCC optimize(3) //#pragma GCC optimize(4) //#pragma GCC optimize(" unroll-loops" ) //#pragma comment(linker, " /stack:200000000" ) //#pragma GCC optimize(" Ofast,no-stack-protector" ) //#pragma GCC target(" sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native" ) #include< bits/stdc++.h> #define fi first #define se second #define db double #define mp make_pair #define pb push_back #define pi acos(-1.0) #define ll long long #define vi vector< int> #define mod 1000000009 #define ld long double //#define C 0.5772156649 #define ls l,m,rt< < 1 #define rs m+1,r,rt< < 1|1 #define pll pair< ll,ll> #define pil pair< int,ll> #define pli pair< ll,int> #define pii pair< int,int> #define ull unsigned long long //#define base 1000000000000000000 #define fin freopen(" a.txt" ," r" ,stdin) #define fout freopen(" a.txt" ," w" ,stdout) #define fio ios::sync_with_stdio(false); cin.tie(0) inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a; } inline void sub(ll & a,ll b){a-=b; if(a< 0)a+=mod; } inline void add(ll & a,ll b){a+=b; if(a> =mod)a-=mod; } template< typename T> inline T const& MAX(T const & a,T const & b){return a> b?a:b; } template< typename T> inline T const& MIN(T const & a,T const & b){return a< b?a:b; } inline ll qp(ll a,ll b){ll ans=1; while(b){if(b& 1)ans=ans*a%mod; a=a*a%mod,b> > =1; }return ans; } inline ll qp(ll a,ll b,ll c){ll ans=1; while(b){if(b& 1)ans=ans*a%c; a=a*a%c,b> > =1; }return ans; } inline ll qm(ll a,ll b,ll c){ll ans=0; while(b){if(b& 1)ans=(ans+a)%c; a=(a+a)%c; b> > =1; }return ans%c; } inline ll qpow(ll a,ll b,ll c){ll ans=1; while(b){if(b& 1)ans=qm(ans,a,c)%c; a=qm(a,a,c)%c; b> > =1; }return ans; }using namespace std; const ull ba=233; const db eps=1e-10; const ll INF=0x3f3f3f3f3f3f3f3f; const int N=200000+10,maxn=100000+10,inf=0x3f3f3f3f; int cnt; ll f[110]; bool check(ll a,ll n,ll x,ll sum){ ll judge=qpow(a,x,n); if (judge==n-1||judge==1)return 1; while (sum--){ judge=qm(judge,judge,n); if (judge==n-1)return 1; } return 0; } bool miller(ll n){ if (n< 2)return 0; if (n==2)return 1; if ((n& 1)==0)return 0; ll x=n-1,sum=0; while (x%2==0)x> > =1,sum++; for (ll i=1; i< =20; i++){ ll a=rand()%(n-1)+1; if (!check(a,n,x,sum))return 0; } return 1; } ll pollard(ll n,ll c){ ll x,y,d,i=1,k=2; x=rand()%n; y=x; while (1){ i++; x=(qm(x,x,n)+c)%n; d=gcd(y-x,n); if (d< 0)d=-d; if (d> 1& & d< n)return d; if (y==x)return n; if (i==k)y=x,k< < =1; } } void Find(ll n){ if(n==1)return; if (miller(n)){ f[cnt++]=n; return ; } ll p=n; while (p> =n) p=pollard(p,rand()%(n-1)+1); Find(n/p); Find(p); } ll a[N],b[N],c[N]; int cal(ll x,ll y) { int ans=0; while(x%y==0)ans++,x/=y; return ans; } void fwt_and(ll *a,int n,int dft) { for(int i=1; i< n; i< < =1) for(int j=0; j< n; j+=i< < 1) for(int k=j; k< j+i; k++) { if(dft==1)a[k]=a[k]+a[i+k]; else a[k]=a[k]-a[i+k]; } } int main() { int n; ll x,y; scanf(" %d%lld%lld" ,& n,& x,& y); if(y%x)return 0*puts(" 0" ); Find(y); sort(f,f+cnt); cnt=unique(f,f+cnt)-f; for(int i=1; i< =n; i++) { scanf(" %lld" ,& a[i]); int p1=0,p2=0; for(int j=0; j< cnt; j++)if(cal(x,f[j])!=cal(y,f[j])) { p1+=(1< < j)*(cal(a[i],f[j])> cal(x,f[j])); p2+=(1< < j)*(cal(a[i],f[j])< cal(y,f[j])); } if(a[i]%x==0)b[p1]++; if(y%a[i]==0)c[p2]++; } fwt_and(b,(1< < cnt),1); fwt_and(c,(1< < cnt),1); for(int i=0; i< (1< < cnt); i++)b[i]=b[i]*c[i]; fwt_and(b,(1< < cnt),-1); printf(" %lld " ,b[0]); return 0; } /****************************************/

//#pragma GCC optimize(2) //#pragma GCC optimize(3) //#pragma GCC optimize(4) //#pragma GCC optimize(" unroll-loops" ) //#pragma comment(linker, " /stack:200000000" ) //#pragma GCC optimize(" Ofast,no-stack-protector" ) //#pragma GCC target(" sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native" ) #include< bits/stdc++.h> #define fi first #define se second #define db double #define mp make_pair #define pb push_back #define pi acos(-1.0) #define ll long long #define vi vector< int> #define mod 1000000009 #define ld long double //#define C 0.5772156649 #define ls l,m,rt< < 1 #define rs m+1,r,rt< < 1|1 #define pll pair< ll,ll> #define pil pair< int,ll> #define pli pair< ll,int> #define pii pair< int,int> #define ull unsigned long long //#define base 1000000000000000000 #define fin freopen(" a.txt" ," r" ,stdin) #define fout freopen(" a.txt" ," w" ,stdout) #define fio ios::sync_with_stdio(false); cin.tie(0) inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a; } inline void sub(ll & a,ll b){a-=b; if(a< 0)a+=mod; } inline void add(ll & a,ll b){a+=b; if(a> =mod)a-=mod; } template< typename T> inline T const& MAX(T const & a,T const & b){return a> b?a:b; } template< typename T> inline T const& MIN(T const & a,T const & b){return a< b?a:b; } inline ll qp(ll a,ll b){ll ans=1; while(b){if(b& 1)ans=ans*a%mod; a=a*a%mod,b> > =1; }return ans; } inline ll qp(ll a,ll b,ll c){ll ans=1; while(b){if(b& 1)ans=ans*a%c; a=a*a%c,b> > =1; }return ans; } inline ll qm(ll a,ll b,ll c){ll ans=0; while(b){if(b& 1)ans=(ans+a)%c; a=(a+a)%c; b> > =1; }return ans%c; } inline ll qpow(ll a,ll b,ll c){ll ans=1; while(b){if(b& 1)ans=qm(ans,a,c)%c; a=qm(a,a,c)%c; b> > =1; }return ans; }using namespace std; const ull ba=233; const db eps=1e-10; const ll INF=0x3f3f3f3f3f3f3f3f; const int N=200000+10,maxn=100000+10,inf=0x3f3f3f3f; int cnt; ll f[110]; bool check(ll a,ll n,ll x,ll sum){ ll judge=qpow(a,x,n); if (judge==n-1||judge==1)return 1; while (sum--){ judge=qm(judge,judge,n); if (judge==n-1)return 1; } return 0; } bool miller(ll n){ if (n< 2)return 0; if (n==2)return 1; if ((n& 1)==0)return 0; ll x=n-1,sum=0; while (x%2==0)x> > =1,sum++; for (ll i=1; i< =20; i++){ ll a=rand()%(n-1)+1; if (!check(a,n,x,sum))return 0; } return 1; } ll pollard(ll n,ll c){ ll x,y,d,i=1,k=2; x=rand()%n; y=x; while (1){ i++; x=(qm(x,x,n)+c)%n; d=gcd(y-x,n); if (d< 0)d=-d; if (d> 1& & d< n)return d; if (y==x)return n; if (i==k)y=x,k< < =1; } } void Find(ll n){ if(n==1)return; if (miller(n)){ f[cnt++]=n; return ; } ll p=n; while (p> =n) p=pollard(p,rand()%(n-1)+1); Find(n/p); Find(p); } ll a[N]; int b[N],c[N]; int cal(ll x,ll y) { int ans=0; while(x%y==0)ans++,x/=y; return ans; } int main() { int n; ll x,y; scanf(" %d%lld%lld" ,& n,& x,& y); if(y%x)return 0*puts(" 0" ); Find(y); sort(f,f+cnt); cnt=unique(f,f+cnt)-f; for(int i=1; i< =n; i++) { scanf(" %lld" ,& a[i]); int p1=0,p2=0; for(int j=0; j< cnt; j++)if(cal(x,f[j])!=cal(y,f[j])) { p1+=(1< < j)*(cal(a[i],f[j])> cal(x,f[j])); p2+=(1< < j)*(cal(a[i],f[j])< cal(y,f[j])); } if(a[i]%x==0)b[p1]++; //,printf(" %d %d " ,i,p1); c[i]=p2; } for(int i=0; i< cnt; i++)for(int j=0; j< (1< < cnt); j++) if(j& (1< < i))b[j]+=b[j^(1< < i)]; ll ans=0; for(int i=1; i< =n; i++) { if(y%a[i]!=0)continue; ans+=b[((1< < cnt)-1)^c[i]]; //printf(" %d %d " ,((1< < cnt)-1)^c[i],b[((1< < cnt)-1)^c[i]]); } printf(" %lld " ,ans); return 0; } /****************************************/