歐拉函數那部分的例題啦，手推一下小數據就可以發先其實是要求最簡（不可再約分）的分數，然后其實就是求歐拉函數啦，記得乘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;}新聞熱點
疑難解答
