首页 > 代码库 > hdu5072 容斥+枚举

hdu5072 容斥+枚举

2024-07-29 01:47:00   217人阅读

这题说的是给了 n 个数字 每个数值大于1 小于100000，n小于100000 ，找出满足下面要求的三人组有多少种 比如abc ( (ab)==(bc)==(ac) ==1 )||( (ab)!=1&&(bc)!=1&&(ac)!=1 )

(()----表示gcd )计算出这样的三元组的个数。

这样考虑 三元组必须满足上面的要求 ， 那么我们减去不满足的可能情况 abc 计算与 a互质的个数 和与a不互质的个数 得到了b在内的不可行的方案数，然后这样发现会多算一次 如果abc

(ab)==1 (ac)!=1 在计算c的时候又会计算一次。 然后我们得到了所有的 不肯能方案除以2 得到了不可能的方案数  总方案数减去不可能方案数就得到了（因为数比较小用容斥便可以计算出答案）

#include <iostream>#include <cstdio>#include <algorithm>#include <cmath>#include<string.h>#include <vector>using namespace std;typedef pair<int,int> PF;bool vis[100005];int prime[10000],num;void pri_p(){   num=0;   memset(vis,false,sizeof(vis));   for(long long i=2; i<=100000; ++i)    if(vis[i]==false){       prime[num++]=i;       for(long long j=i*i; j<=100000; j+=i) vis[j]=true;   }}int A[100005];int P[15];int sizea[100005];int D[100005];vector<PF>F[100005];void fenjie(int loc,int len){    for(int s=1; s<(1<<len); ++s){       int ss=1,num=0;       for(int i=0;i<len ;++i){           if(s&(1<<i)){             ss*=P[i]; num++;           }       }       F[loc].push_back(make_pair(ss,num));   }   sizea[loc]=F[loc].size();}void inti(){    pri_p();    for(int i=1; i<=100000; ++i){            int len=0;            int s=i,num=0;            while(s>1&&prime[num]!=0){                 if(s%prime[num]==0){                    P[len++]=prime[num];                    while(s>1&&s%prime[num]==0){                         s/=prime[num];                    }                 }                 num++;            }        fenjie(i,len);    }}void sum(int loc){      int sz=sizea[loc];      for(int i=0; i<sz; ++i){           PF t=F[loc][i];           D[t.first]++;      }}int jud(int loc){    int ans=0;    for(int i=0; i<sizea[loc]; ++i){        PF f=F[loc][i];        if(f.second%2==1)ans+=D[f.first];        else ans-=D[f.first];    }    return ans;}int main(){    inti();    int cas;    scanf("%d",&cas);    for(int cc=1; cc<=cas; ++cc){        long long n;        scanf("%I64d",&n);        memset(D,0,sizeof(D));        for(int i=0; i<n; ++i){            scanf("%d",&A[i]);            sum(A[i]);        }        long long ans=0;        for(int i=0; i<n; ++i){         long long    S= jud(A[i]);             long long noeven = n-S;             if(S<=1||noeven==0) continue;             ans = ans+noeven*(S-1);        }        printf("%I64d\n",n*(n-1)*(n-2)/6-ans/2);    }    return 0;}
View Code

 

hdu5072 容斥+枚举


联系
我们