【bzoj2190】【SDOI2008】仪仗队（数论）

2019-11-14 10:03:19

字体：大中小

来源：转载

供稿：网友

欧拉函数那部分的例题啦，手推一下小数据就可以发先其实是要求最简（不可再约分）的分数，然后其实就是求欧拉函数啦，记得乘2已经对于1手动加，反正乱搞一下就出来了

#include<iostream> #include<cstdio>#include<cstring>#include<string>#include<algorithm>using namespace std;int n,ans;const int N=80000;int p[N],phi[N],PRime[N];void graph(){ phi[1]=1; for (int i=2;i<=n;i++) { if (!p[i]) { prime[++prime[0]]=i; phi[i]=i-1; } for (int j=1;j<=prime[0]&&i*prime[j]<=n;++j) { p[i*prime[j]]=1; if (i%prime[j]==0) { phi[i*prime[j]]=phi[i]*prime[j]; break; } else phi[i*prime[j]]=phi[i]*(prime[j]-1); } }}int main(){ cin>>n; memset(p,0,sizeof(p)); memset(phi,0,sizeof(phi)); if (n==1){cout<<1;return 0;} graph(); for (int i=2;i<n;i++) ans+=phi[i]; ans*=2; ans+=3; cout<<ans;}

上一篇：java多线程学习总结（一）

下一篇：[LeetCode]15.3Sum