题目地址：http://poj.org/problem?id=2478
对于每个分母，既约真分数的个数就是小于n的与n互质的个数，即欧拉函数的值φ(n)n
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;
typedef long long LL;
void phi_table(int n,LL *phi)
{for(int i=1;i<=n;i++) phi[i]=0;phi[0]=1;for(int i=2;i<=n;i++)if(!phi[i]) //每一项i都是素数for(int j=i;j<=n;j+=i) //i的倍数肯定都包含这个素因数 {if(!phi[j]) phi[j]=j; //未计算的初始化为j,为了计算式子n*(1-1/p)中的n;phi[j]=phi[j]/i*(i-1);}
}
LL phi[1000000+5];
int main()
{phi_table(1000000+3,phi);int n;while(cin>>n&&n){LL sum=0;for(int i=2;i<=n;i++) sum+=phi[i];cout<<sum<<endl;}return 0;
}