LIGHTOJ 1007 – MATHEMATICALLY HARD【欧拉函数】

版权声明：转载请注明出处。 https://blog.csdn.net/u014427196/article/details/46383193

题目链接： http://www.lightoj.com/volume_showproblem.php?problem=1007

题意：打表欧拉函数即可；

代码：

#include<stdio.h>    
#include<iostream>    
#include<math.h>    
#include<stdlib.h>    
#include<ctype.h>    
#include<algorithm>    
#include<vector>    
#include<string.h>    
#include<stack>    
#include<set>    
#include<map>    
#include<sstream>    
#include<time.h>    
#include<utility>    
#include<malloc.h>    
#include<stdexcept>    
#include<iomanip>    
#include<iterator>    

using namespace std;

const int MAXN = 5000010; 

int t;
int from, ed;
bool com[MAXN];
int primes, prime[MAXN];
unsigned long long phi[MAXN];

void init(int n)
{

    phi[1] = 0;
    for (int i = 2; i <= n; ++i)
    {
        if (!com[i])
        {
            prime[primes++] = i;
            phi[i] = i - 1;
        }
        for (int j = 0; j < primes && i*prime[j] <= n; ++j)
        {
            com[i*prime[j]] = true;
            if (i % prime[j])
                phi[i*prime[j]] = phi[i] * (prime[j] - 1);
            else
            {
                phi[i*prime[j]] = phi[i] * prime[j]; break;
            }
        }
    }

    phi[2] *= phi[2];
    for (int i = 3; i <= n; i++)
        phi[i] = phi[i - 1] + phi[i] * phi[i];
}

int main()
{
    init(5000005);
    scanf("%d",&t);
    for (int i = 1; i <= t; i++)
    {
        scanf("%d%d",&from,&ed);
        printf("Case %d: %llu\n",i,phi[ed] - phi[from-1]);
    }
    return 0;
}