HDU 2824 The Euler function

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

题目链接

百度百科上欧拉函数的解释：

在数论，对正整数n，欧拉函数是小于n的正整数中与n互质的数的数目（φ(1)=1）。

这道题主要运用欧拉函数的几个公式对范围内的数字进行打表：

1. φ(1)=1（唯一和1互质的数(小于等于1)就是1本身）。
2. 若m,n互质，φ(mn)=φ(m)φ(n)若m,n互质，φ(mn)=φ(m)φ(n)
3. 若n为质数则φ(n)=n-1若n为质数则φ(n)=n-1
4. 

AC代码:

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <iomanip>
#include <cctype>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <cstdlib>
#include <sstream>

using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int maxn = 3000010;

int Sum[maxn];
bool IsPrime[maxn];
int Prime[maxn];

void Judge() {
    int cnt = 0;
    mem(IsPrime, 0);
    for (int i = 2;i < maxn;++i) {
        if (IsPrime[i] == 0) {
            Prime[cnt++] = i;
            Sum[i] = i - 1;
        }
        for (int j = 0;j < cnt && i * Prime[j] < maxn;++j) {
            IsPrime[i * Prime[j]] = 1;
            if (i % Prime[j] == 0) {
                Sum[i * Prime[j]] = Sum[i] * Prime[j];
            }
            else {
                Sum[i * Prime[j]] = Sum[i] * (Prime[j] - 1);
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    Judge();
    int a,b;
    while (cin >> a >> b) {
        ll Res = 0;
        for (int i = a;i <= b;++i) {
            Res += Sum[i];
        }
        cout << Res << endl;
    }
    return 0;
}