首先介绍下什么是欧拉函数吧，欧拉函数phi(x)代表小于等于x的数中和x互质的数的个数(小于显然只对1成立)， 比如说小于等于9的数中与9互质的有1,2,4,5,7,8,则phi(9)=6.求phi(x)得公式由欧拉给出(神一般的男人，几何学，数论，统计学，物理学，统计学，据说连金融学都有以欧拉命名的公式，膜拜…….) 欧拉指出，以phi(x)表示小于等于x的数中与x互质的数的个数可以这样得到：
phi(x) = x * (1 - 1/p1) * (1-1/p2) * (1 - 1 / p3)…..*(1 - 1/pn)
其中p1,p2,p3….pn是x的所有质因数，每个质因数只使用一次，使用上述公式，则phi(9)=9*(1-1/3)=6.
如果只是单纯求解某一个数的欧拉值，这是很简单的，对这个数分解质因数求解即可，如果x不是很大，甚至你直接用gcd来求也行，但是，如果我们要求解1-100万的所有数的欧拉函数值，上述的做法便太耗时间了，做法并不难，效仿素数筛法，我们有对应欧拉筛法.
欧拉筛法的原理如下，我们观察phi(x)的求解式子，首先另phi(x)=x,然后仿照素数筛法，如果x能被2,3,5,7….这些素数筛到，则执行phi(x)=phi(x)*(1-1/prime)
代码如下，一看就明白
//欧拉筛法,快速筛出1-100万的欧拉函数值 const int maxn = 1000000; int phi[maxn+1]; bool isPrime[maxn+1]; void Eular() { for(int i=1;i<=maxn;i++) phi[i]=i; memset(isPrime,true,sizeof(isPrime)); isPrime[0]=isPrime[1]=false; phi[1]=0; for(int i=2;i<=maxn;i++) { if(isPrime[i]) { for(int j=i;j<=maxn;j+=i) { isPrime[j]=false; phi[j] -= phi[j]/i; } } } }好吧，我也是今天才学会这个筛法，素数筛法还有一种更快的接近O(n)的筛法，叫做线性素数筛法，对应的，欧拉函数筛法也有一个线性的，有兴趣自己google吧.
今天写的一道用上此知识点的题目： LightOj 1370 题目链接
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int maxn = 1100000; int phi[maxn+1]; bool isPrime[maxn+1]; int mp[maxn+1]; //欧拉筛法,快速筛出1-100万的欧拉函数值 void Eular() { for(int i=1;i<=maxn;i++) phi[i]=i; memset(isPrime,true,sizeof(isPrime)); isPrime[0]=isPrime[1]=false; phi[1]=0; for(int i=2;i<=maxn;i++) { if(isPrime[i]) { for(int j=i;j<=maxn;j+=i) { isPrime[j]=false; phi[j] -= phi[j]/i; } } } } void getMap() { memset(mp,0,sizeof(mp)); for(int i=1;i<=maxn;i++) // the length of bamboo { for(int j=phi[i];j>=0 && mp[j]==0;j--) mp[j]=i; } } int main() { int T,cas=1; scanf("%d" ,&T); Eular(); getMap(); while(T--) { int n,x; scanf("%d",&n); long long sum=0; for(int i=0;i<n;i++) { scanf("%d" ,&x); sum+=mp[x]; } printf("Case %d: %lld Xukha\n",cas++,sum); } return 0; }