lightoj1007

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

27 8月 2015

1007 - Mathematically Hard

In this problem, you will be given two integers a and b. You have to find the summation of the scores of the numbers from a to b (inclusive). The score of a number is defined as the following function.Mathematically some problems look hard. But with the help of the computer, some problems can be easily solvable.

score (x) = n², where n is the number of relatively prime numbers with x, which are smaller than x

For example,

For 6, the relatively prime numbers with 6 are 1 and 5. So, score (6) = 2² = 4.

For 8, the relatively prime numbers with 8 are 1, 3, 5 and 7. So, score (8) = 4² = 16.

Now you have to solve this task.

Input

Input starts with an integer T (≤ 10⁵), denoting the number of test cases.

Each case will contain two integers a and b (2 ≤ a ≤ b ≤ 5 * 10⁶).

Output

For each case, print the case number and the summation of all the scores from a to b.

Sample Input	Output for Sample Input
36 68 82 20	Case 1: 4Case 2: 16Case 3: 1237

题目类型：欧拉函数

算法分析：使用递推的方法将5e6以内的欧拉函数值算出来，进而求前缀和，最后直接查询即可，注意本题数据比较大，只能使用unsigned long long定义euler数组

#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 = 5000000 + 66;

unsigned long long euler[maxn];

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

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

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

void init ()
{
   euler[1] = euler[1] * euler[1];

    for (int i = 2; i < maxn; i++)
        euler[i] = euler[i-1] + euler[i] * euler[i];

}


int main()
{
//    freopen ("aaa.txt", "r", stdin);

    GetEuler ();

    init ();

    int t, flag = 1;
    scanf ("%d", &t);

    while (t--)
    {
        printf ("Case %d: ", flag++);

        int a, b;
        scanf ("%d%d", &a, &b);

        printf ("%llu\n", euler[b] - euler[a-1]);
    }

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 = 5000000 + 66;

unsigned long long euler[maxn];

void GetEuler ()

{

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

euler[i] = i;

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

euler[i] >>= 1;

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

{

if (euler[i] == i)

{

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

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

}

void init ()

{

euler[1] = euler[1] * euler[1];

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

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

}

int main()

{

// freopen ("aaa.txt", "r", stdin);

GetEuler ();

init ();

int t, flag = 1;

scanf ("%d", &t);

while (t--)

{

printf ("Case %d: ", flag++);

int a, b;

scanf ("%d%d", &a, &b);

printf ("%llu\n", euler[b] - euler[a-1]);

}

return 0;

}

lightoj1002

lightoj1008

一	二	三	四	五	六	日
« 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

超客的水墨烟雨

lightoj1007

Input

Output

Sample Input

Output for Sample Input

分类目录

标签云

书签

近期评论