poj2478

maksyuki 发表于 oj 分类，标签: 数论-欧拉函数

15 9月 2015

Farey Sequence

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.

Input

There are several test cases. Each test case has only one line, which contains a positive integer n (2 <= n <= 10⁶). There are no blank lines between cases. A line with a single 0 terminates the input.

Output

For each test case, you should output one line, which contains N(n) ---- the number of terms in the Farey sequence Fn.

Sample Input

Sample Output

Source

POJ Contest,Author:Mathematica@ZSU

题目类型：法雷级数

算法分析：法雷级数F(n)等于小于等于n的所有欧拉函数值之和，所以先使用递推求得欧拉值表，然后构造前缀和表，最后直接查表输出即可

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>

#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int MOD = 7;
const int maxn = 1000000 + 66;

long long euler[maxn];

void GetEuler ()
{
    for (long long i = 0; i < maxn; i++)
        euler[i] = i;

    for (long long i = 2; i < maxn; i += 2)
        euler[i] >>= 1;

    for (long long i = 3; i < maxn; i += 2)
    {
        if (euler[i] == i)
        {
            for (long long j = i; j < maxn; j += i)
                euler[j] = euler[j] - euler[j] / i;
        }
    }
}

int main()
{
//    ifstream cin ("aaa.txt");

    GetEuler ();

    for (long long i = 1; i < maxn; i++)
        euler[i] += euler[i-1];

    long long val;
    while (cin >> val)
    {
        if (val == 0)
            break;

        cout << euler[val] - 1<< endl;
    }

return 0;
}

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

#define lson rt << 1, l, m

#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int MOD = 7;

const int maxn = 1000000 + 66;

long long euler[maxn];

void GetEuler ()

{

for (long long i = 0; i < maxn; i++)

euler[i] = i;

for (long long i = 2; i < maxn; i += 2)

euler[i] >>= 1;

for (long long i = 3; i < maxn; i += 2)

{

if (euler[i] == i)

{

for (long long j = i; j < maxn; j += i)

euler[j] = euler[j] - euler[j] / i;

}

int main()

{

// ifstream cin ("aaa.txt");

GetEuler ();

for (long long i = 1; i < maxn; i++)

euler[i] += euler[i-1];

long long val;

while (cin >> val)

{

if (val == 0)

break;

cout << euler[val] - 1<< endl;

}

return 0;

}

poj2456

poj2479

一	二	三	四	五	六	日
« 6月
		1	2	3	4	5
6	7	8	9	10	11	12
13	14	15	16	17	18	19
20	21	22	23	24	25	26
27	28	29	30	31

超客的水墨烟雨

poj2478

分类目录

标签云

书签

近期评论