题目大意
直接看原文吧。。。。
The Farey Sequence Fn for any integer n with n >= 2 is the set of irreducible rational numbers a/b with 0 < a < b <= n and gcd(a,b) = 1 arranged in increasing order. The first few are
F2 = {1/2}
F3 = {1/3, 1/2, 2/3}
F4 = {1/4, 1/3, 1/2, 2/3, 3/4}
F5 = {1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5}
You task is to calculate the number of terms in the Farey sequence Fn.
题解
欧拉函数的一个应用~~对于输入n，答案就等于phi[1]+phi[2]+……phi[n]
代码：
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#define MAXN 1000005
using namespace std;
int phi[MAXN],prime[MAXN],check[MAXN];
void euler_phi()
{
int cnt=0;
memset(check,false,sizeof(check));
phi[1]=1;
for(int i=2; i<MAXN; i++)
{
if(!check[i])
{
prime[cnt++]=i;
phi[i]=i-1;
}
for(int j=0; j<cnt&&i*prime[j]<MAXN; j++)
{
check[i*prime[j]]=true;
if(i%prime[j]==0)
{
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
else
phi[i*prime[j]]=phi[i]*(prime[j]-1);
}
}
}
int main()
{
int n;
euler_phi();
while(cin>>n&&n)
{
long long sum=0;
for(int i=2; i<=n; i++)
sum+=phi[i];
cout<<sum<<endl;
}
return 0;
}