LINK
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 ,n<x and gcd(n,x)=1
To illustrate, 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, 5}. So, score (6) = 22 = 4.
For 16, the relatively prime numbers with 16 are {1, 3, 5, 7, 9, 11, 13, 15}. So, score (16) = 82 = 64.
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
- 题意：t组样例，每组有a,b两个数，求a到b之间每个数的欧拉函数的平方再求和；
- 分析：数据过多，用欧拉函数质数打表
- ac代码：
#include<stdio.h>
#include<algorithm>
using namespace std;
typedef long long ll;
ll sum[5000010];
void init()//质数打表
{
int i,j;
for(i=0;i<5000010;i++)
sum[i]=i;//给n赋初值
for(i=2;i<5000010;i++)
if(sum[i]==i)//质数
{
for(j=i;j<5000010;j+=i)//质数去找与它互质的数
sum[j]=sum[j]/i*(i-1);
}
for(i=1;i<5000010;i++)//此时sum还存储它之前的score和
sum[i]=sum[i-1]+sum[i]*sum[i];
}
int main()
{
init();
int t,cas=1;
scanf("%d",&t);
while(t--)
{
int a,b;
scanf("%d%d",&a,&b);
printf("Case %d: %llu\n",cas++,sum[b]-sum[a-1]);
}
}
/*欧拉函数：求小于n有多少个数是相对n的质数的：推导后为sum=n/i*(i-1)
ans=n;
for(i=2;i<=n/i;i++)
{
if(n%i==0)
{
ans=ans/i*(i-1);
while(n%i==0)
n=n/i;
}
}
if(n>1)
ans=ans/n*(n-1);
这是暴力，样例数小于10万，n小于500万，单个样例最多是5万次，50000*100000会超时；
*/