题目：http://acm.hdu.edu.cn/showproblem.php?pid=4556
题目：根据题目要求，求解出答案，看题目中的图，找出其中的规律
学到的东西：关于分数类的递推关系，要多联系欧拉函数（欧拉函数求解n比n小与n互素的个数也包括1，所以如果以x作为分母，那么它能构成的真分数且不可约分即为x的欧拉函数值）
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N=1e6+10;
#define ll __int64
//const int mod=1e9+7;
ll phi[N];
void Euler(){
phi[1]=1;
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);//先进行除法是为了防止中间数据的溢出
}
void solve()
{
phi[1]=3;
//for(int i=2;i<20;i++) cout<<phi[i]<<" ";
for(int i=2;i<N;i++)
phi[i]=(2*phi[i]+phi[i-1]);
}
int main()
{
Euler();
solve();
int x;while(~scanf("%d",&x)){
printf("%I64d\n",phi[x]);
}
}
