[原创]Light OJ 1007 Mathematically Hard [欧拉函数+前缀和]【数论】

2016-06-28 21:36:41 Tabris_ 阅读数：674

博客爬取于2020-06-14 22:44:21
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/51778975

Mathematically Hard

Time Limit:2000MS Memory Limit:65536KB 64bit IO Format:%lld & %llu
Submit

Status
Description
Mathematically some problems look hard. But with the help of the computer, some problems can be easily solvable.

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.

score (x) = n2, 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) = 22 = 4.

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

Now you have to solve this task.

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

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

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

Sample Input
3
6 6
8 8
2 20
Sample Output
Case 1: 4
Case 2: 16
Case 3: 1237

题目大意 就是求a~b的所有数的欧拉函数的和

题解：数据量5e6 预处理一下 将所有欧拉函数的平方求出 在处理一下前缀和 即可 因为后面的大数会爆long long 所以要用unsign long long

附本题代码

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
# include <stdio.h>
# include <stdlib.h>
# include <string.h>
# include <limits.h>
# include <malloc.h>
# include <ctype.h>
# include <math.h>
# include <string>
# include <iostream>
# include <algorithm>
# include <map>
# include <vector>
# include <set>

using namespace std;

# define LL unsigned long long int

/*
const double eps = 1e-7;
const double Pi = acos(-1.0);
*/

LL phi[5000500];


void phi_table()  //欧拉函数。。。
{
    int i,j;
    for(i=2; i<=5e6; i++)
        phi[i]=0;
    phi[1]=1;
    for(i=2; i<=5e6; i++)
        if(!phi[i])
            for(j=i; j<=5e6; j+=i)
            {
                if(!phi[j])
                    phi[j]=j;
                phi[j]=phi[j]/i*(i-1);
            }
    phi[0]=0;
}
void init()
{
    for(int i=2; i<5000001; i++)
    {
        phi[i]=phi[i-1]+phi[i]*phi[i] ;
    }
    return ;
}

int main()
{
    phi_table();
    init();
    int t,aa,bb,p=0;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&aa,&bb);

        printf("Case %d: %llu\n",++p,phi[bb]-phi[aa-1]);
    }
    return 0;
}