LightOj 1007 - Mathematically Hard

---

Solving Tips :: Euler's totient function

---

 // Verdict : Accepted

#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#include <string>
#include <vector>
#include <cmath>
#include <cctype>
#include <sstream>
#include <set>
#include <list>
#include <stack>
#include <queue>
#include <algorithm>
#define sf scanf
#define pf printf
#define sfint scanf ("%d %d",&a,&b)
#define sfl scanf ("%ld %ld",&a,&b)
#define sfll scanf ("%lld %lld",&a,&b)
#define sfd scanf ("%lf %lf",&a,&b)
#define sff scanf ("%f %f",&a,&b)
#define lp1(i,n) for(i=0;i<n;i++)
#define lp2(i,n) for(i=1;i<=n;i++)
#define LL long long
#define L long
#define mem(c,v) memset(c,v,sizeof(c))
#define ui unsigned int
#define ull unsigned long long int
#define nl puts("")
#define MX 5000009
#define N 100
#define MOD 10000000007
#define pb push_back
#define pi acos(-1.0)
#define sz size()
#define gc getchar ()
#define ps push
#define clr clear
#define bn begin()
#define ed end()

using namespace std;

int prime[MX+5]; // generating bit wise seieve 

int setbit(int n, int pos)
{
    n = n|(1<<pos);
    return n;
}

bool checkbit(int n, int pos)
{
    n=n&(1<<pos);
    return n;
}

void seieve(int n)
{
    int i,j,x=sqrt(n);

    prime[0]=setbit(prime[0],0);
    prime[0]=setbit(prime[0],1);

    for(i=4;i<=n;i+=2)
    {
        prime[i>>5] = setbit(prime[i>>5],i&31);
    }

    for(i=3;i<=x;i+=2)
    {
        if(!checkbit(prime[i>>5],i&31))
        {
            for(j=i+i;j<=n;j+=i)
            {
                prime[j>>5] = setbit(prime[j>>5],j&31);
            }
        }
    }
}

ull phi[MX+5];

void euler_phi()
{
    ull i,k,p;

    for(i=1;i<=MX;i++) phi[i]=i;

    for(p=2;p<=MX;p++)
    {
        if(!checkbit(prime[p>>5],p&31))
        {
            if(phi[p]==p)
            {
                for(k=p;k<=MX;k+=p)
                {
                    phi[k]-=phi[k]/p;
                }
            }
        }
    }
}

int main()
{
    seieve(MX);
    euler_phi();
    ull i;
    for(i=2;i<=MX;i++)
    {
        phi[i]=phi[i-1]+(phi[i]*phi[i]);
    }

    ull t,tc,x,y;
    sf("%llu",&tc);
    for(t=1;t<=tc;t++)
    {
        sf("%llu %llu",&x,&y);
        pf("Case %llu: %llu\n",t,phi[y]-phi[x-1]);
    }

    return 0;
}

---

---

Version :: 02

#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#include <string>
#include <vector>
#include <cmath>
#include <cctype>
#include <sstream>
#include <set>
#include <list>
#include <stack>
#include <queue>
#include <algorithm>
#define sf scanf
#define pf printf
#define sfint scanf ("%d %d",&a,&b)
#define sfl scanf ("%ld %ld",&a,&b)
#define sfll scanf ("%lld %lld",&a,&b)
#define sfd scanf ("%lf %lf",&a,&b)
#define sff scanf ("%f %f",&a,&b)
#define lp1(i,n) for(i=0;i<n;i++)
#define lp2(i,n) for(i=1;i<=n;i++)
#define LL long long
#define L long
#define mem(c,v) memset(c,v,sizeof(c))
#define ui unsigned int
#define ull unsigned long long int
#define nl puts("")
#define MX 5000009
#define N 100
#define MOD 10000000007
#define pb push_back
#define pi acos(-1.0)
#define sz size()
#define gc getchar ()
#define ps push
#define clr clear
#define bn begin()
#define ed end()

using namespace std;

bool stats[MX];

void seieve()
{
    mem(stats,false);
    ull i,j,qrt;

    stats[0]=stats[1]=true;

    for(i=4;i<=MX;i+=2) stats[i]=true;

    qrt = (unsigned long) sqrt(double(MX));

    for(i=3;i<=qrt;i+=2)
    {
        if(!stats[i])
        {
            for(j=i*i;j<=MX;j+=i+i)
            {
                stats[j]=true;
            }
        }
    }
}

ull phi[MX];

void euler_phi()
{
    ull i,k,p;

    for(i=1;i<MX;i++) phi[i]=i;

    for(p=2;p<MX;p++)
    {
        if(!stats[p])
        {
            if(phi[p] == p)
            {
                for(k=p;k<MX;k+=p)
                {
                    phi[k]-=phi[k]/p;
                }
            }
        }
    }
}

int main()
{
    seieve();
    euler_phi();

    ull i,j,t,tc;

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

    sf("%llu",&tc);

    for(t=1;t<=tc;t++)
    {
        ull x,y;

        sf("%llu %llu",&x,&y);

        pf("Case %llu: %llu\n",t,phi[y]-phi[x-1]);
    }

    return 0;
}