Farey Sequence POJ - 2478

题目链接：

题目：

法理序列Fn是指对于任意整数n( n >= 2)，由不可约的分数a/b（0 < a < b <= n），gcd(a,b) = 1升序排列构成的序列，最开始的几个如下

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}

你的任务是计算法理序列Fn中的元素个数。

Input

输入包含多组样例. 每组样例仅一行, 有一个正整数n (2 <= n <= 10

⁶). 两组样例间无空行. 0代表输入结束.

Output

对于每种情况，你需要输出法理序列Fn中包含元素的个数

Sample Input

Sample Output

1359 思路： 1=1 3=1+2 5=1+2+2 9=1+2+2+4 ... 由于1 2 2 4 4 ... 是欧拉值，故很容易想到是求欧拉值的前缀和，所以第一步将欧拉值打表出来，后来我一开始遍历用for循环求 和，超时了，所以这里还是要将前缀和存入表内，由于是从下标为2开始的，故求前缀和从下标为3开始

//// Created by hanyu on 2019/8/9.//#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include
            
             #include
             using namespace std;typedef long long ll;const int maxn=2e6+7;ll euler[maxn];void value(){ memset(euler,0,sizeof(euler)); euler[1]=1; for(int i=2;i<=maxn;i++) { if(!euler[i]) { for(int j=i;j<=maxn;j+=i) { if(!euler[j]) euler[j]=j; euler[j]=euler[j]/i*(i-1); } } } for(int i=3;i<=maxn;i++) euler[i]+=euler[i-1];}int main(){ int n; value(); while(~scanf("%d",&n)&&n) { printf("%lld\n",euler[n]); } return 0;}