暑假算法回顾之------欧拉函数
首先怼上通项公式：
欧拉函数的通式：φ(n)=n(1-1/p1)(1-1/p2)(1-1/p3)*(1-1/p4)……(1-1/pn)*,其中p1, p2……pn为n的所有质因数，n是不为0的整数。φ(1)=1（唯一和1互质的数就是1本身）。
求单个数的欧拉数 long long eular(long long n){ long long ans = n; for(int i = 2; i*i <= n; i++) { if(n % i == 0) { ans -= ans/i; //等价于通项，把n乘进去 while(n % i == 0) //确保下一个i是n的素因数 n /= i; } } if(n > 1)ans -= ans/n; //最后可能还剩下一个素因数没有除 return ans;} 打表欧拉 void init(){ memset(sum, 0, sizeof(sum)); for(int i = 2; i < N; i++) phi[i] = i; for(int i = 2; i < N; i++) { if(phi[i] == i) for(int j = i; j < N; j += i) phi[j] = phi[j] / i * (i - 1); }} 线性欧拉筛 const int maxn=1000100;long long prim[maxn];long long phi[maxn]; bool ju[maxn]={0};long long qian[maxn];void oula(int n){int tot=0;for (int i=2;i<=n;++i){if(!ju[i]){tot++;prim[tot]=i;phi[i]=i-1;}for(int j=1;j<=tot;j++){if(i*prim[j]>n)break;ju[i*prim[j]]=1;if(i%prim[j]==0){phi[i*prim[j]]=phi[i]*prim[j];break;}phi[i*prim[j]]=phi[i]*phi[prim[j]];}}} 欧拉函数性质
①N>1，不大于N且和N互素的所有正整数的和是 1/2Neular(N)。 推荐题目：HDOJ 3501 题解：点击打开链接
②若(N%a== 0 && (N/a)%a==0) 则有:E(N)=E(N/a)*a;
③若(N%a==0 && (N/a)%a!=0) 则有:E(N)=E(N/a)*(a-1);
4：如果n是质数p的k次幂，那么φ(n)=p^k-1*(p-1)
5：欧拉函数是积性函数——若m,n互质，φ(mn)=φ(n)*φ(m)，积性函数和完全积性函数有区别，有兴趣可以自己百度一下
6：当n为奇数的时候，φ(2n)=φ(n)，这一点是由性质2推出来的，因为2必定和所有的奇数都是互质的，所以而φ(2)=1。所以得出这个结果
7：n的所有质因子之和等于φ(n)*n/2（这不算性质，只能算延伸）。