欧拉函数那部分的例题啦，手推一下小数据就可以发先其实是要求最简（不可再约分）的分数，然后其实就是求欧拉函数啦，记得乘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; }