「luogu2714」四元组统计

 1 #include<bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 const int N=10010,maxn=10000;
 5 int n,a[N],u[N],p[N],totp;
 6 ll f[N];
 7 bool isp[N];
 8 inline ll calc(ll k){return k*(k-1)*(k-2)*(k-3)/4/3/2;}
 9 void solve(){
10     memset(a,0,sizeof(a));
11     memset(f,0,sizeof(f));
12     int t;
13     ll ans=0;
14     for(int i=1;i<=n;i++) scanf("%d",&t),a[t]++;
15     for(int i=1;i<=maxn;i++){
16         for(int j=i;j<=maxn;j+=i) f[i]+=a[j];
17         if(f[i]>3) f[i]=calc(f[i]);
18         else f[i]=0;
19     }
20     for(int i=1;i<=maxn;i++) ans+=f[i]*u[i];
21     printf("%lld
",ans);
22     return;
23 }
24 int main(){
25     isp[1]=1,u[1]=1;
26     for(int i=2;i<=maxn;i++){
27         if(!isp[i]) p[++totp]=i,u[i]=-1;
28         for(int j=1;j<=totp&&p[j]*i<=maxn;j++){
29             isp[p[j]*i]=1;
30             if(!(i%p[j])) break;
31             u[p[j]*i]=-u[i];
32         }
33     }
34     while(scanf("%d",&n)!=EOF) solve();
35     return 0;
36 }