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)

InputThere are several test cases. Each line has two integers a, b (2<a<b<3000000).OutputOutput the result of (a)+ (a+1)+....+ (b)Sample Input

3 100

Sample Output

3042
思路：欧拉函数前缀和板子

typedef long long LL;

const int maxm = 3e6+5;

LL Euler[maxm];

void getEuler() {
    Euler[1] = 1;
    for(int i = 2; i <= maxm; ++i) {
        if(!Euler[i]) {
            for(int j = i; j <= maxm; j += i) {
                if(!Euler[j]) Euler[j] = j;
                Euler[j] = Euler[j] / i * (i-1);
            }
        }
    }
}

int main() {
    int a, b;
    getEuler();
    for(int i = 2; i <= maxm; ++i)
        Euler[i] += Euler[i-1];
    while(scanf("%d%d", &a, &b) != EOF) {
        printf("%lld\n", Euler[b] - Euler[a-1]);
    }
    return 0;
}

View Code