Friday 28 July 2017

Lightoj 1054 - Efficient Pseudo Code

  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 (% 2==1){
  27.              number = (number * x) % mod;
  28.              }
  29.         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. */

No comments:

Post a Comment

Most Featured Post

Lightoj 1159 - Batman

http://lightoj.com/volume_showproblem.php?problem=1159 problem analysis: First i thought of this as if s1, s2 and s3 are those three str...