学步园

这道题用到了线性筛法求素数，关于线性筛法求素数可以参看http://blog.csdn.net/titikdhu/archive/2010/07/22/5754172.aspx。

这道题我们可以发现一个规律，设f[n]表示n阶Farey Sequence的的元素个数，则f[n]与f[n-1]之间的差值即为以n为分母，以小于n且与n互质的数为分子组成的真分数的个数，其实就是小于或等于n的正整数中与n互质的数的数目，这正式欧拉函数（Eular‘s totient function）的定义,可以参看中文wikihttp://zh.wikipedia.org/zh-cn/%E6%AC%A7%E6%8B%89%E5%87%BD%E6%95%B0或者英文wikihttp://en.wikipedia.org/wiki/Euler's_totient_function。

则我们得到递推公式，f[n]=f[n-1]+eular[n]，所以题目的关键转化为求欧拉函数值，由欧拉函数的性质“欧拉函数是积性函数，即是说若m,n互质，”和“若x为质数，则eular[x]=x-1”可以得出如下定理：

若(maxn%a==0 && (maxn/a)%a==0) 则有:eular[N]=eular[maxn/a]*a;(这条式子还没想明白)

若(maxn%a==0 && (maxn/a)%a!=0) 则有:eular[N]=eular[maxn/a]*(a-1);

再结合线性筛法求素数，就可以得到一下的代码：

#include <iostream><br /> #include <cstring><br /> using namespace std;<br /> const int maxn=1000000;<br /> bool isprime[maxn+1];<br /> long long prime[maxn+1]={0};<br /> long long eular[maxn+1]={0};<br /> long long f[maxn+1]={0};<br /> int len;<br /> void initialize()<br /> {<br /> len=0;<br /> memset(isprime,true,sizeof(isprime));<br /> for (int i=2;i<=maxn;i++)<br /> {<br /> if (isprime[i])<br /> {<br /> prime[++len]=i;<br /> eular[i]=i-1;<br /> }<br /> for (int j=1;j<=len && prime[j]*i<=maxn;j++)<br /> {<br /> isprime[prime[j]*i]=false;<br /> if (i%prime[j]==0)//判断prime[j]是否为最小质因子<br /> {<br /> eular[i*prime[j]]=eular[i]*prime[j];<br /> break;<br /> }<br /> else eular[i*prime[j]]=eular[i]*(prime[j]-1);<br /> }<br /> }<br /> }<br /> int main()<br /> {<br /> int n;<br /> eular[1]=0;<br /> initialize();<br /> for (int i=2;i<=maxn;i++)<br /> f[i]=f[i-1]+eular[i];<br /> while (cin>>n && n)<br /> {<br /> cout<<f[n]<<endl;<br /> }<br /> return 0;<br /> }<br />  

PS：太晚了...困...代码分析以后再说吧...