fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long 
  4. #define mod (ll) 1200000090
  5. #define N 40000005
  6. int  lp[N+1];
  7. vector<int > pr;
  8. void solve(){
  9. for (int  i=2; i<=N; ++i) {
  10.     if (lp[i] == 0) {
  11.         lp[i] = i;
  12.         pr.push_back (i);
  13.     }
  14.     for (int  j=0; j<(ll )pr.size() && pr[j]<=lp[i] && i*pr[j]<=N; ++j)
  15.         lp[i * pr[j]] = pr[j];
  16. }
  17. }
  18.  
  19. ll  po(ll  a,ll  n){
  20.   ll  res=a, ans=1;
  21.   while(n){
  22.     if(n%2) ans=ans*res%mod;
  23.     res=res*res%mod;
  24.     n/=2;
  25.   }
  26.   return ans;
  27. }
  28. ll  aka(ll  p, ll  alpha){
  29.   if(alpha==0) return 1;
  30.   if(alpha==1) return (p+1)%mod;
  31.   if(alpha%2==1) return (p*aka(p,alpha-1)%mod+1)%mod;
  32.   if(alpha%2==0) return ((po(p,alpha/2)+1)*((aka(p,alpha/2)-1+mod)%mod)%mod+1)%mod;
  33. }
  34. ll  f(ll  n){
  35.   ll  tmp,i=0,so_mu,res=1;
  36.   while(pr[i]<=n){
  37.     tmp=pr[i];
  38.     so_mu=0;
  39.     while(tmp<=n){
  40.         so_mu = so_mu+ (n/tmp);
  41.         tmp=tmp*pr[i];
  42.     }
  43.     res=res*aka(pr[i],so_mu*3)%mod;
  44.     //res=res*(so_mu+1)*(so_mu+2)/2%mod;
  45.     i++;
  46.   }
  47.   return res;
  48. }
  49. int main(){
  50.     ios_base::sync_with_stdio(false);
  51.     cin.tie(NULL);
  52.     ll  n,res,testcase;
  53.     solve();
  54.     cin>>testcase;
  55.    while(testcase--){
  56.       cin>>n;
  57.       if(n==0) break;
  58.       res=f(n);
  59.       cout<<res<<'\n';
  60.    }
  61. }
Success #stdin #stdout 0.33s 175828KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/wyJnwO
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!