LightOJ - 1340 - Strory Of Tomisu Ghost

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

Idea :



Code First Then See Solution

 Code :

 #include <bits/stdc++.h>

using namespace std;

#define mx 100006
#define mod 10000019
#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 c)
{
    if(c==0)
        return 1;
    if(c%2==0)
    {
        ll x=bigmod(a,c/2)%mod;
        return (x*x)%mod;
    }
    else
    {
        ll x=a%mod;
        ll y=bigmod(a,c-1)%mod;
        return (x*y)%mod;
    }
}

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