Lightoj 1054 - Efficient Pseudo Code

http://lightoj.com/volume_showproblem.php?problem=1054

1. #include<bits/stdc++.h>
2. using namespace std;
3. #define srt 65540
4. #define mod 1000000007
5. typedef long long ll;
6. ll prime[srt];
7.  ll k,t;
8. void seive()
9. {
10.     bool ara[srt];
11.     memset(ara,0,sizeof(ara));
12.     for(int i=2,k=0;i<srt;i++){
13.         if(ara[i]==0){
14.                 prime[k++]=i;
15.                 for(int j=i;j<srt;j=i+j)
16.                     ara[j]=1;
17.         }
18.         t=k;
19.     }
20. }
21. ll Pow (ll x,ll y)
22.  {
23.      ll number = 1;
24.      while (y>0)
25.      {
26.          if (y % 2==1){
27.              number = (number * x) % mod;
28.              }
29.         x = (x * x) % mod;
30.          y>>=1;
31.  
32.      }
33.     return number;
34.  }
35. ll  sum(ll a,ll b)
36. {
37.       ll total,res;
38.         res=(Pow(a,b)-1)%mod;
39.            res=(res*Pow(a-1,mod-2))%mod;
40.         return (res+mod)%mod;//to avoid negative numbers
41.  
42. }
43. int main()
44. {
45.     ll n,m,cnt,num,T,l=0,total;
46.     cin>>T;
47.      seive();
48.     while(T--){
49.     scanf("%lld%lld",&n,&m);
50.     total=1;
51.     for(int i=0;i<t;i++){
52.            cnt=0;
53.            num=0;
54.         if(n%prime[i]==0){
55.                 num=prime[i];
56.                 while(n%prime[i]==0){
57.                     n/=prime[i];
58.                     cnt++;
59.                 }
60.                 total=(total*sum(num,cnt*m+1))%mod;
61.  
62.         }
63.  
64.     }
65.    if(n!=1){
66.         total=(total*sum(n,m+1))%mod;
67.  
68.     }
69.  
70.      printf("Case %lld: %lld\n",++l,total);
71.     }
72.  
73.     return 0;
74. }
75.  
76.  
77. /*
78. #include <bits/stdc++.h>
79. using namespace std;
80. #define M 1000000007
81. #define N 66000
82. #define ll long long int
83. vector<int> primes;
84. bool sieve[N];
85. void pre(){
86.     memset(sieve, true, sizeof(sieve));
87.     for(ll i = 2; i <N; i++){
88.         if(sieve[i]) primes.push_back(i);
89.         for(ll j = 2*i;j <N; j+=i){
90.             sieve[j] = false;
91.         }
92.     }
93.     //for(int i = 0; i <primes.size(); i++) cout<<primes[i]<<" ";  
94. }
95.  
96. ll bigmod(ll p, ll q){
97.     if(q == 1) return p%M;
98.     if(q%2 == 0){
99.         ll a = bigmod(p, q/2);
100.         //cout<<"hdbfd";
101.         return ((a%M)*(a%M))%M;
102.     }
103.     else{
104.         //cout<<"hey";
105.         ll a = bigmod(p, q-1);
106.         return (a*p)%M;
107.     }
108. }
109. int main(){
110.     pre();
111.     int ts;
112.     cin>>ts;
113.     for(int l = 1;  l <= ts; l++){
114.         int a, b;
115.         scanf("%d%d", &a, &b);
116.         ll ans = 1;
117.         int k = 0;
118.         while(a!=1){
119.             if(k == primes.size() || primes[k]>a) break;
120.             int c = 0;
121.             int p = primes[k];
122.             if(a%p == 0){
123.                 while(a%p == 0){
124.                     a/=p;
125.                     c++;
126.                 }
127.             ans = (ans*((bigmod((ll)p , (ll)c*b+1)-1+M)%M* (bigmod(p-1,M-2) + M)%M)%M)%M;
128.             ans = ans%M;
129.             }
130.             k++;   
131.         }
132.         if(a!= 1){
133.         ans = ans * ((bigmod(a,b+1)-1+M)%M * (bigmod(a-1, M-2)+M)%M)%M;
134.         ans = ans%M;
135.         }
136.         printf("Case %d: %lld\n",l, ans);
137.     }
138.     return 0;
139. }
140.  
141.  
142. */