首页 > 代码库 > HDU 2824 The Euler function 题解

HDU 2824 The Euler function 题解

2024-07-10 02:01:27   213人阅读

求区间的euler数值，自然使用筛子法了。

Problem Description
The Euler function phi is an important kind of function in number theory, (n) represents the amount of the numbers which are smaller than n and coprime to n, and this function has a lot of beautiful characteristics. Here comes a very easy question: suppose you are given a, b, try to calculate (a)+ (a+1)+....+ (b)
 

Input
There are several test cases. Each line has two integers a, b (2<a<b<3000000).
 

Output
Output the result of (a)+ (a+1)+....+ (b)
 

Sample Input
3 100
 

Sample Output
3042

#include <stdio.h>

const int MAX_SZIE = 3000001;
__int64 phi[MAX_SZIE] = {0};
void eulerPhi()
{
	for (int i = 2; i < MAX_SZIE; i++)
	{
		if (!phi[i])
		{
			for (int j = i; j < MAX_SZIE; j += i)
			{
				if (!phi[j]) phi[j] = j;
				phi[j] = phi[j] / i * (i - 1);
			}
		}
	}
	for (int i = 3; i < MAX_SZIE; i++)
	{
		phi[i] += phi[i-1];
	}
}

int main()
{
	eulerPhi();
	int a, b;
	while (scanf("%d %d", &a, &b) != EOF)
	{
		printf("%I64d\n", phi[b] - phi[a-1]);
	}
	return 0;
}


联系
我们