HDU 2824 The Euler function 题解

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

3 100

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;
}

HDU 2824 The Euler function 题解,布布扣,bubuko.com

HDU 2824 The Euler function 题解

原文：http://blog.csdn.net/kenden23/article/details/35784531