首页 > 代码库 > 【POJ3904】【P1202】水晶密码
【POJ3904】【P1202】水晶密码
说是莫比乌斯反演，其实只是玩儿玩儿内个miu函数而已……
原题：
wty 打算攻击 applepi 的用来存放机密数据的水晶系统。 applepi 早有察觉，于是布置了一个密码系统来防备 wty 的攻击。 wty 经过研究发现，applepi 的密码系统中最关键的部分在于一 串四个正整数组成的密钥，四个正整数的顺序可以任意排列， 并且这四个正整数的最大公约数为 1。
wty 已经成功地把这四个正整数限制在了 N 个正整数构成的集合中，但是，密钥的数目 可能仍然是很庞大的。wty 希望知道有多少组可能的密钥。当然，applepi 已经挫败了 wty 的阴谋，但是他对这个问题也是饶有兴趣的。所以说，现在你需要帮助 applepi 算出有多少 组可能密钥，为 applepi 评估他的水晶系统的安全性提供参考。
N≤10000，集合中的数不大于 10000
题目要求四个数gcd为1，可以求出不为1的有几个，然后用总数减
先通过枚举数来求出共有num[i]个数含有因子i，c(num[i],4)即为gcd为i的情况个数，使用容斥去掉2*3和6这样的重复计算即可
手玩小数据可以发现，搞容斥的+或-的情况刚好和miu符合，比如2应该-，miu就是-1,6应该+，miu就是1之类的，所以就可以直接用miu来计算是过程变得更高端
核心代码：if(_num>=4) ans+=miu[k]*_num*(_num-1)*(_num-2)*(_num-3)/24;
需要注意一点，求num[i]的时候直接枚举会T，要用sqrt优化，最后根据miu求ans的时候是直接从1枚举到maxx（最大的内个数），但是求num[i]的时候不能枚举到sqrt(maxx)，而是枚举到sqrt(a[i])
代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #include<cmath> 6 using namespace std; 7 int read(){int z=0,mark=1; char ch=getchar(); 8 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)mark=-1; ch=getchar();} 9 while(ch>=‘0‘&&ch<=‘9‘){z=(z<<3)+(z<<1)+ch-‘0‘; ch=getchar();}10 return z*mark;11 }12 int n,a[51000];13 bool kang[51000]; int zhi[51000],ztop=0;14 int miu[51000];15 int num[510000];16 void get_miu(){17 memset(kang,0,sizeof(kang));18 miu[1]=1;19 for(int i=2;i<=50000;i++){20 if(!kang[i]){ zhi[++ztop]=i; miu[i]=-1;}21 for(int j=1;zhi[j]*i<=50000;j++){22 kang[zhi[j]*i]=true;23 if(i%zhi[j]==0){ miu[zhi[j]*i]=0; break;}24 miu[zhi[j]*i]=-miu[i];25 }26 }27 }28 int main(){//freopen("ddd.in","r",stdin);29 get_miu();30 while(scanf("%d",&n)!=EOF){31 memset(num,0,sizeof(num));32 int maxx=0;33 for(int i=1;i<=n;i++){ a[i]=read(); maxx=max(maxx,a[i]);}34 if(n<4){ cout<<0<<endl; continue;}35 for(int i=1;i<=n;i++){36 int smax=int(sqrt(a[i]*1.0));37 for(int j=1;j<=smax;j++)if(a[i]%j==0){38 num[j]++;39 if(a[i]/j!=j) num[a[i]/j]++;40 }41 }42 long long ans=0;43 for(int k=1;k<=maxx;k++){44 long long _num=num[k];45 if(_num>=4) ans+=miu[k]*_num*(_num-1)*(_num-2)*(_num-3)/24;46 }47 cout<<ans<<endl;48 }49 return 0;50 }
【POJ3904】【P1202】水晶密码