很经典的一道容斥原理问题。
设$k|gcd(a,b,c,d)$,则说明$k$均为$a,b,c,d$的约数,因此转化一下题意,也就是
容斥原理($k=1$(的倍数)的情况-$k=2$(的倍数)的情况-$k=3$(的倍数)的情况+$k=6$(的倍数)的情况$\cdots$)。
因此只需要求出约数$k$出现的次数$t$就好了,方案数即为$C_{t}^{4}$。
(不懂的话去看看算法进阶上Zap上的讲述)
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#define ll long long
#define gc getchar()
using namespace std;
const int N=1e4+5;
const int M=101;
inline void qr(int &x)
{
x=0;char c=gc;int f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
x*=f;
}
void qw(ll x)
{
if(x<0)x=-x,putchar('-');
if(x/10)qw(x/10);
putchar(x%10+48);
}
int prime[M],m;bool v[M];
void gp()
{
for(int i=2;i<=100;i++)
{
if(!v[i])prime[++m]=i;
for(int j=1;j<=m&&i*prime[j]<=100;j++)
{
v[i*prime[j]]=1;
if(i%prime[j]==0)break;
}
}
}
int num[N],a[N],p[M],sz;
void ins(int x)
{
sz=0;
for(int i=1;i<=m&&prime[i]*prime[i]<=x;i++)
if(x%prime[i]==0)
{
p[++sz]=prime[i];
while(x%p[sz]==0)x/=p[sz];
}
if(x>1)p[++sz]=x;
for(int i=1;i<(1<<sz);i++)
{
int t=1,cnt=0;
for(int k=sz-1;~k;k--)if(i>>k&1)
{
t*=p[k+1];++cnt;
}
++a[t];if(!num[t])num[t]=cnt;
}
}
ll c[N];
int main()
{
gp();for(int i=4;i<=10000;i++)c[i]=1ll*i*(i-1)*(i-2)*(i-3)/24;
int n;
while(scanf("%d",&n)!=EOF)
{
memset(a,0,sizeof(a));int mx=0;
for(int i=1,x;i<=n;i++)qr(x),ins(x),mx=max(x,mx);
ll ans=0;
for(int i=1;i<=mx;i++)if(a[i]>3)
{
if(num[i]&1)ans+=c[a[i]];
else ans-=c[a[i]];
}
qw(c[n]-ans);puts("");
}
return 0;
}
最后一次更新于2019-09-28
0 条评论