LightOj 1054 - Efficient Pseudo Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<map>

#define sf scanf
#define pf printf
#define S 1000100

using namespace std;

typedef long long LL;
typedef pair<LL, LL> pll;

const int mod = 1000000007;

int prime[(S>>6) + 1] , prm[(S>>1) + 9], plen=0;

#define setbit(n) (prime[n>>6] |= (1 << ((n>>1)&31)))
#define checkbit(n) (prime[n>>6] & (1 << ((n>>1)&31)))

void sieve()
{
    LL i,j;

    for(i=3; i*i<S; i+=2)
    {
        if(!checkbit(i))
        {
            for(j=i*i; j<S; j+=(2*i))
            {
                setbit(j);
            }
        }
    }

    prm[plen++] = 2;

    for(i=3; i<S; i+=2)
    {
        if(!checkbit(i))
        {
            prm[plen++] = i;
        }
    }

    //for(i=0; i<100; i++) cout << prm[i] << " ";
}

LL big_mod(LL a, LL b)
{
    if(!b)
    {
        return 1;
    }

    if(b&1)
    {
        return (a * big_mod(a , b-1)) % mod;
    }

    else
    {
        LL x = big_mod(a , b/2);

        return (x*x) % mod;
    }
}

pll EGCD(LL a, LL b)
{
    if(!b)
    {
        return pll(1,0);
    }

    else
    {
        pll d = EGCD(b, a%b);

        return pll(d.second, d.first - (a / b) * d.second);
    }
}

LL mod_inverse(LL a, LL m)
{
    pll r = EGCD(a , m);
    return ((r.first % m) + m) % m;
}

void solution(LL n , LL ex)
{
    LL pwr=0 , ans=1 , x=1 , y=1;

    for(int i=0; i<plen and prm[i] * prm[i] <=n; i++)
    {
        if(!(n%prm[i]))
        {
            pwr=0;
            x = 1;

            while(!(n%prm[i]))
            {
                pwr++;
                n/=prm[i];
                if(n==0 or n==1) break;
            }

            x = ( x * big_mod(prm[i] , (pwr * ex) + 1) - (1 % mod) ) % mod;
            x = x * mod_inverse(prm[i] - 1 , mod) ;
            x = x % mod;
            ans = (ans * x) % mod;
        }
    }

    if(n > 1)
    {
        x = 1;
        x = (x * big_mod(n , 1+ex) - ( 1 % mod)) % mod;
        x =   x * mod_inverse(n - 1 , mod) ;
        x = x % mod;
        ans = (ans * x) % mod;
    }

    if(ans < 0) // This condition will be executed when you have impossible inverse_mod
    {
        ans = 1;
    }

    pf("%lld\n" , ans);
}

int main()
{
    sieve();
    //freopen("out.txt" , "w", stdout);
    int t, tc=0;
    LL num, m;
    sf("%d", &t);
    while(t--)
    {
        sf("%lld %lld", &num, &m);
        pf("Case %d: ", ++tc);
        solution(num, m);
    }

    return 0;
}