Farey Sequence POJ - 2478 (欧拉函数前缀和）

ゞ浴缸里的玫瑰 2023-08-17 15:40 111阅读 0赞

# Farey Sequence POJ - 2478 #

题目链接：[https://vjudge.net/problem/POJ-2478][https_vjudge.net_problem_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 6). 两组样例间无空行. 0代表输入结束.

Output

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

Sample Input

2
    3
    4
    5
    0

Sample Output

1
    3
    5
    9
    思路：
    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 <algorithm>
    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <queue>
    #include <set>
    #include<math.h>
    #include<map>
    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;
    }

# #

转载于:https://www.cnblogs.com/Vampire6/p/11329981.html

[https_vjudge.net_problem_POJ-2478]: https://vjudge.net/problem/POJ-2478