LightOJ - 1054 - Efficient Pseudo Code

Problem Link : lightoj.com/volume_showproblem.php?problem=1054

Idea :We need find out the SOD value of n^m.If the prime factorization of n is,


p1^q1 * p2^q2 *.....*pn^qn then,
 sum of divisor = (1+p1+p1^2+..+p1^q1)*(1+p2+p2^2+..+p2^q2)*.....*(1+pn+pn^2+..+p1^qn)

to find p1^q1 there is a geometric equation,
   x=p1^(q1+1)-1/(p1-1)

but the value of p1^q1 is very large so we need to mod this value by 1000000007.We can easily do this by using BIGMOD.For p1-1 we need to find MODINVERSE of p1-1.Then multiply this value which is (p1-1)^-1 with  
p1^(q1+1)-1.


Code first Then See Solution

Code :

 #include <bits/stdc++.h>

using namespace std;

#define  mx 100006
#define mod 1000000007
#define ll long long

bitset <mx+10> b;
vector <ll> v;

void seive()
{
    b.set();
    b[0]=b[1]=false;
    for(ll i=2;i<mx;i++)
    {
        if(b[i])
        {
            v.push_back(i);
            for(ll j=i*i;j<mx;j+=i)
                b[j]=false;
        }
    }
}

ll bigmod(ll a,ll b)
{
   if(b==0)
        return 1;
   if(b%2==0)
   {
       ll x=bigmod(a,b/2)%mod;
       return (x*x)%mod;
   }
   else
   {
       ll x=a%mod;
       ll y=bigmod(a,b-1)%mod;
       return (x*y)%mod;
   }
}

ll modinverse(ll a)
{
    return bigmod(a,mod-2);
}

int main()
{
    int t,f=0;
    seive();
    cin>>t;
    while(t--)
    {
        f++;
        ll n,m,res1=1,res2=1,sum=1,s;
        cin>>n>>m;
        for(ll i=0;i<v.size()&&v[i]<=sqrt(n);i++)
        {
            if(n%v[i]==0)
            {
                ll cnt=0;
                while(n%v[i]==0)
                {
                    cnt++;
                    n/=v[i];
                }
                cnt*=m;
                cnt++;
                res1= bigmod(v[i],cnt);
                res2 = modinverse(v[i]-1);
                s=((res1-1+mod)%mod*(res2+mod%mod))%mod;
                sum=((sum%mod)*(s%mod))%mod;
                }
        }
        if(n>1)
        {
            ll cnt=m+1;
            res1=bigmod(n,cnt);
            res2 = modinverse(n-1);
            s=((res1-1+mod)%mod*(res2+mod)%mod)%mod;
            sum =((sum%mod)*(s%mod))%mod;
            }
        cout<<"Case "<<f<<": "<<sum<<endl;
    }
    return 0;
}