https://vj.xtuacm.cf/contest/view.action?cid=57#problem/I
1.当需要求1到N的欧拉数之和时用线性方法（本题）
2.当需要求单个欧拉数但数据很大用标准方法求
例如：https://vj.xtuacm.cf/contest/view.action?cid=57#problem/H
线性的方法求欧拉数代码（模板）：
#include<stdio.h>#include<string.h>#define ll long longconst int MAXN=1000010;int dp[MAXN];ll a[MAXN];int main(){ memset(dp,0,sizeof(dp)); dp[1]=1; for(int i=2; i<MAXN; i++) { if(dp[i])continue; for(int j=i; j<MAXN; j+=i) { if(!dp[j])dp[j]=j; dp[j]=dp[j]/i*(i-1); } } a[1]=1; a[2]=1; for(int i=3;i<=MAXN;i++) a[i]=a[i-1]+dp[i]; int N; while(~scanf("%d",&N),N) { printf("%I64dn",a[N]); } return 0;}普通方法求欧拉数：https://vj.xtuacm.cf/contest/view.action?cid=57#problem/H
#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <vector>#include <set>#include <queue>#define ll long longusing namespace std;int a[4000],c[5000],d[40010];int cnt;void init()//筛选出质数{ int num=0; memset(d,1,sizeof(d)); for(int i=2;i<=40000;i++) { if(d[i]) { for(int j=2*i;j<=40000;j=j+i) d[j]=0; c[num++]=i; } }}void fen(int n)//分解质因数{ cnt=0; for(int i=0;c[i]*c[i]<=n;i++) { if(n%c[i]==0) { a[cnt++]=c[i]; while(n%c[i]==0) n=n/c[i]; } } if(n>1) a[cnt++]=n;}int main(){ init(); int n; while(~scanf("%d",&n),n) { memset(a,0,sizeof(a)); fen(n); int l=n; for(int i=0;i<cnt;i++)//得出结果 l=l-l/a[i]; cout<<l<<endl; } return 0;}