题目：

3 100

3042

题目分析：

欧拉函数,简单题。

直接暴力这道题就能过。。。。下面简介一下欧拉函数的一些知识。

1、定义：对于正整数n，φ(n)是小于或等于n的正整数中，与n互质的数的数目。

　　　　比如：φ(8)=4。由于1。3，5，7均和8互质。

2、性质：1）若p是质数。φ(p)= p-1.

　　　2）若n是质数p的k次幂，φ(n)=(p-1)*p^(k-1)。由于除了p的倍数都与n互质

　　　3）欧拉函数是积性函数，若m,n互质，φ(mn)= φ(m)φ(n).

　　依据这3条性质我们就能够推出一个整数的欧拉函数的公式。由于一个数总能够写成一些质数的乘积的形式。

　　E(k)=(p1-1)(p2-1)...(pi-1)*(p1^(a1-1))(p2^(a2-1))...(pi^(ai-1))

　　　　= k*(p1-1)(p2-1)...(pi-1)/(p1*p2*...*pi)

　　　　= k*(1-1/p1)*(1-1/p2)...(1-1/pk)

在程序中利用欧拉函数例如以下性质，能够高速求出欧拉函数的值（a为N的质因素）

　　若( N%a ==0&&(N/a)%a ==0)则有：E(N)= E(N/a)*a;

　　若( N%a ==0&&(N/a)%a !=0)则有：E(N)= E(N/a)*(a-1);

代码例如以下：

/*

 * a1.cpp

 *

 *  Created on: 2015年3月19日

 *      Author: Administrator

 */

#include <iostream>

#include <cstdio>

using namespace std;

const int maxn = 3000001;

int phi[maxn];

/**

 * 初始化欧拉数组.

 * phi[8]: 表示从1~8与8互质的元素的个数

 *

 */

void prepare(){

	int i;

	for(i = 1 ; i < maxn ; ++i){

		phi[i] = i;

	}

	int j;

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

		if(phi[i] == i){

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

				phi[j] = phi[j]/i*(i-1);

			}

		}

	}

}

int main(){

	prepare();

	int a,b;

	while(scanf("%d%d",&a,&b)!=EOF){

		long long ans = 0;

		int i;

		for(i = a ; i <= b ; ++i){//暴力求phi[a]到phi[b]之间的和

			ans += phi[i];

		}

		printf("%lld\n",ans);

	}

	return 0;

}

下面贴一个TLE了的版本号：

TLE的原因非常仅仅管，由于每次算phi[i],它都掉了一次phi()。运算量太大。

/*

 * POJ_2407.cpp

 *

 *  Created on: 2013年11月19日

 *      Author: Administrator

 */

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

typedef long long ll;

const int maxn = 1000015;

bool u[maxn];

ll su[maxn];

ll num;

ll gcd(ll a, ll b) {

	if (b == 0) {

		return a;

	}

	return gcd(b, a % b);

}

void prepare() {//欧拉筛法产生素数表

	ll i, j;

	memset(u, true, sizeof(u));

	for (i = 2; i <= 1000010; ++i) {

		if (u[i]) {

			su[++num] = i;

		}

		for (j = 1; j <= num; ++j) {

			if (i * su[j] > 1000010) {

				break;

			}

			u[i * su[j]] = false;

			if (i % su[j] == 0) {

				break;

			}

		}

	}

}

ll phi(ll x) {//欧拉函数,用于求[1,x)中与x互质的整数的个数

	ll ans = 1;

	int i, j, k;

	for (i = 1; i <= num; ++i) {

		if (x % su[i] == 0) {

			j = 0;

			while (x % su[i] == 0) {

				++j;

				x /= su[i];

			}

			for (k = 1; k < j; ++k) {

				ans = ans * su[i] % 1000000007ll;

			}

			ans = ans * (su[i] - 1) % 1000000007ll;

			if (x == 1) {

				break;

			}

		}

	}

	if (x > 1) {

		ans = ans * (x - 1) % 1000000007ll;

	}

	return ans;

}

int main(){

	prepare();

	long long a;

	long long b;

	while(scanf("%lld%lld",&a,&b)!=EOF){

		long long ans = 0;

		long long i;

		for(i = a ; i <= b ; ++i){

			ans += phi(i);

		}

		printf("%lld\n",ans);

	}

	return 0;

}