HDUOJ 5072 Coprime

题目链接http://acm.hdu.edu.cn/showproblem.php?pid=5072

题意:给你n个数,数出有多少三元组(a,b,c)满足三个数相互互质或相互不互质。

思路:直接数很难数,不如考虑逆问题,即数出满足一对互质,一对不互质,则我们可以枚举每个数,求出与它不互质的数,剩下的数就是与它互质的数了。问题就变成要求解n个数中有多少数与a[i]不互质,我们直接对a[i]分解质因数,然后容斥计算答案即可,最后拿总数去减就好了。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
const int N=100000+10;
int T,n,i,j,k,a[N],cnt[N];
int main(){
    for (read(T);T--;){
        read(n);
        memset(cnt,0,sizeof(cnt));
        for (i=1;i<=n;i++) cnt[read(a[i])]++;
        for (i=2;i<=100000;i++){
            for (j=i+i;j<=100000;j+=i){
                cnt[i]+=cnt[j];
            }
        }
        ll res=0;
        for (i=1;i<=n;i++){
            vector<int>fac;
            int m=(int)sqrt(a[i]+0.5);
            for (j=2;j<=m;j++){
                if (a[i]%j==0){
                    fac.push_back(j);
                    while (a[i]%j==0) a[i]/=j;
                }
            }
            if (a[i]>1) fac.push_back(a[i]);
            int tot=1<<(int)fac.size();
            ll num=0;
            for (j=1;j<tot;j++){
                int mul=1,bit=0;
                for (k=0;k<(int)fac.size();k++){
                    if (j&(1<<k)){
                        bit++;
                        mul*=fac[k];
                    }
                }
                if (bit&1) num+=cnt[mul]-1;
                else num-=cnt[mul]-1;
            }
            res-=num*(n-num-1);
        }
        res/=2LL;
        res+=(ll)n*(n-1)*(n-2)/6;
        printf("%lld\n",res);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注