天码

这题不难,重要是理解吧..我发现自己越来越菜了.
求任意四个gcd为1,并不好求,但是它的对立面就很明显了,就是有相同的约数.那么我们就可以分解每个数的约数,显然这是一个莫比乌斯函数.
又或者说莫比乌斯函数和容斥关系很大,对于总的方案数挺显然就是C(n,4).对于每个数,我们先进行质因数分解,然后进行合成因数,对于2,3这样的因数,我们显然是-,而对于6来说,因为我们-了关于2的约数,又-了关于3的约数,我们就要+回来,具体来说就是个莫比乌斯函数.
代码如下:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e4+5;
ll a[N];
ll cnt[N];//记录每个因子个数
ll sum[N];//记录每个因子是由多少个质因子合成.
ll prime[N];
ll p[N];
void solve(ll x)
{
    ll tot=0;
    for(ll i=2;i*i<=x;i++)
    {
        if(x%i==0)
        {
            prime[tot++]=i;
            while(x%i==0)   x/=i;
        }
    }
    if(x!=1)    prime[tot++]=x;
    for(ll i=0;i<(1<<tot);i++)
    {
        ll vnt=0,k=1;
        for(ll j=0;j<tot;j++)
        {
            if(i>>j&1)
            {
                k*=prime[j];
                vnt++;
            }
        }
        sum[k]=vnt;
        cnt[k]++;
    }
}

int main()
{
    int n;
    for(ll i=4;i<=N-5;i++)
    {
        p[i]=i*(i-1)*(i-2)*(i-3)/24;
    }//C(i,4).
    while(cin>>n)
    {
        memset(cnt,0,sizeof cnt);
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            solve(a[i]);
        }
        ll lpt=0;
        for(ll i=2;i<=N;i++)
        {
            if(sum[i]&1)    lpt+=p[cnt[i]];
            else            lpt-=p[cnt[i]];
        }
        cout<<p[n]-lpt<<endl;
    }
    return 0;
}