现在的位置: 首页 > 综合 > 正文

POJ-2478-Farey Sequence 解题报告

2018年04月21日 ⁄ 综合 ⁄ 共 692字 ⁄ 字号 评论关闭

       求欧拉函数表题。题意:法雷序列Fn对于任何一个大于等于2的n来说是这么一种序列,它是由最简真分数a/b构成,0 < a < b <= n且a与b互质。现在给你n,求法雷序列Fn里面数的个数。


       我的解题思路:水题,对于2~n中每一个数的欧拉函数之和就是答案了。


       我的解题代码:

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <algorithm>

using namespace std;

const int N = 1000001;

int phi[N];
long long ans[N];

void Init();

void GetPhi(int maxn);

int main()
{
    Init();
    int n;
    while (~scanf("%d", &n) && n)
    {
        printf("%lld\n", ans[n]);
    }
    return 0;
}

void Init()
{
    memset(phi, 0, sizeof(phi));
    phi[1] = 1;
    GetPhi(N);
    ans[1] = 0;
    for (int i=2; i<N; ++i) ans[i] = phi[i] + ans[i-1];
    return;
}

void GetPhi(int maxn)
{
    memset(phi, 0, sizeof(phi));
    phi[1] = 1;
    for (int i=2; i<maxn; ++i)
    {
        if (!phi[i])
        {
            for (int j=i; j<maxn; j+=i)
            {
                if (!phi[j]) phi[j] = j;
                phi[j] -= phi[j] / i;
            }
        }
    }
    return;
}

抱歉!评论已关闭.