题目：
The Euler function
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 166 Accepted Submission(s): 96
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
Source
2009 Multi-University Training Contest 1 – Host by TJU
Recommend
gaojie
题目分析：
欧拉函数,简单题。直接暴力这道题就能过。。。。
代码如下：
/* * 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;}
旅游不在乎终点，而是在意途中的人和事还有那些美好的记忆和景色。
