#include <stdio.h> int main() { int N,num=0; scanf("%d",&N); if(N==1) printf("%d\n",N-1); if(N==2) printf("%d\n",N+1); if(N>=3&&N<=40000) { int m=N-1; while(m>=1) { int ans=m; N=m; for(int i=2;i*i<=N;i++) { if(N%i==0) { ans*=(i-1)*1.0/i; while(N%i==0) N/=i*1.0; } } if(N>1) ans*=(N-1)*1.0/N; m--; num+=ans; } printf("%d\n",num*2+1); } return 0; }
欧拉函数实际应用,省赛提高题,今日份学习