1007 - Mathematically Hard

Problem link : http://lightoj.com/volume_showproblem.php?problem=1007

Solution Idea : This problem teaches you the use of unsigned long long data type.The problem is the modified application Euler Phy's algorithm .

Solution :

#include<bits/stdc++.h>

using namespace std;

bool status[5000005];

vector<int>prime;

void sieve()
{
    int n=5000000;
    int sq=sqrt(n);

    for(int i=4; i<=n; i=i+2) status[i]=true;

    for(int i=3; i<=sq; i=i+2)
    {
        if(status[i]==false)
        {

            for(int j=i*i; j<=n; j=j+i) status[j]=true;
        }
    }
    status[1]=1;
    status[0]=1;

    prime.push_back(2);

    for(int i=3; i<=n; i=i+2)
    {
        if(status[i]==false) prime.push_back(i);
    }
}


unsigned long long  phi[5000505];

int main()
{

    sieve();

    for (int i = 1; i <= 5000000; i++)
    {
        phi[i] = i;
    }

    int w,tr;
    for (int p = 0; p < prime.size(); p++)
    {
        w=prime[p];
        for (int k = w; k <= 5000000; k =k+w)
        {
            phi[k] -= phi[k] / w;


        }

    }
    phi[1]=0;
    phi[0]=0;

    for(int i=1; i<=5000000; i++ )
    {
        phi[i]=phi[i]*phi[i];
        phi[i]=phi[i]+phi[i-1];
    }

    long long int t,a,b;

    scanf("%lld",&t);
    unsigned long long temp;

    for(long long int ca=1; ca<=t; ca++)
    {
        scanf("%lld%lld",&a,&b);
        temp=phi[b]-phi[a-1];
        printf("Case %lld: %llu\n",ca,phi[b]-phi[a-1]);
    }
}