poj 3904 Sky Code

本文主要是介绍poj 3904 Sky Code，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：

http://poj.org/problem?id=3904

这道容斥题一开始我看得比较懵逼，因为要求的是4个数的gcd=1的不好求，就去找反面：gcd不等于1的
也就是找gcd=2的个数，然后在这里面找4个数就是$C_n^4$
同理找gcd=3的个数，在这里面找4个数
。。。
然后会有重的比如说6，计算2 的时候会计算到，3的时候又会被计算到
然后我就去看怎么计算这个容斥的系数。。。。结果就是莫比乌斯函数啊T_T，我TMD的竟然没反应过来T_T

#include"iostream"
#include"cstring"
#include"vector"
#include"map"
using namespace std;
typedef long long LL;
const int maxn=1e4+5;
const int MOD=1e9+7;
int cnt1[maxn];//cnt[i]表示含有i这个因子的数有多少个
int mu[maxn];
vector<LL>prime;
void PHI(int n)//筛出莫比乌斯函数 
{bool vis[maxn];memset(vis,1,sizeof(vis));for(int i=2; i<=n; i++){if(vis[i]){prime.push_back(i);mu[i]=1;}for(int j=0; j<prime.size()&&i*prime[j]<=n; j++){vis[i*prime[j]]=0;if(i%prime[j]==0)break;else mu[i*prime[j]]=-mu[i];}}
}
void fenjie(LL n)//分解n的所有因子 
{for(LL i=1;i*i<=n;i++){if(n%i==0){cnt1[i]++;if(i==n/i)continue;cnt1[n/i]++;}}
}
LL f(LL n)//计算C(n,4)
{return n*(n-1)*(n-2)*(n-3)/24;
}
int main()
{PHI(maxn-5);int N;while(cin>>N){memset(cnt1,0,sizeof cnt1);int Max=0;for(int i=1; i<=N; i++){int t;cin>>t;fenjie(t);Max=max(Max,t);}LL ans=0;for(int d=2; d<=Max; d++)//容斥计算所有因子不是1的和{if(cnt1[d]==0)continue;ans+=f(cnt1[d])*mu[d];//用莫比乌斯函数来容斥 }cout<<f(N)-ans<<endl;} 
}

这篇关于poj 3904 Sky Code的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---