fork(1) download
copy 
  1.  
  2. #include<bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6. typedef long long           ll;
  7. typedef unsigned long long  ull;
  8.  
  9. #define sf                  scanf
  10. #define pf                  printf
  11. #define pb                  push_back
  12. #define ppb                 pop_back
  13. #define MP                  make_pair
  14. #define PF                  first
  15. #define PS                  second
  16. #define FOR(i,x,y)          for(i=x;i<y;i++)
  17. #define RFOR(i,x,y)         for(i=x;i>=y;i--)
  18. #define CLR(arr,val)        memset(arr,val,sizeof arr);
  19. #define vout(v)             for(i=0;i<v.size();i++){ cout<<v[i]; if(i<v.size()-1) cout<<' '; else cout<<endl;}
  20. #define TCL(test,t)         for(test=1;test<=t;test++)
  21. #define READ()              freopen("input.txt", "r", stdin)
  22. #define WRITE()             freopen("output.txt", "w", stdout)
  23. #define MAXN 100000008
  24. #define MOD 4294967296
  25.  
  26. ll v=MAXN,val[MAXN];
  27. vector <int> prime;
  28. bool a[MAXN];
  29.  
  30. void sieve()
  31. {
  32.     ll i,t,j,n,m,k=0;
  33.     m=sqrt(v);
  34.     prime.pb(2);
  35.     k=1;
  36.     a[0]=1;
  37.     a[1]=1;
  38.     a[2]=0;
  39.     val[1]=1;
  40.     val[2]=2;
  41.     for(i=2;i<MAXN;i=i*2){
  42.         val[i]=2;
  43.     }
  44.     for(i=4;i<v;i+=2){
  45.         a[i]=1;
  46.     }
  47.     for(i=3;i<v;i+=2){
  48.         if(a[i]==0){
  49.             prime.pb(i);
  50.             k++;
  51.             if(i<=m){
  52.                 for(j=i*i;j<v;j+=2*i){
  53.                     a[j]=1;
  54.                 }
  55.             }
  56.             for(j=i;j<v;j=j*i){
  57.                 val[j]=i;
  58.             }
  59.         }
  60.  
  61.     }
  62.     //cout<<k<<endl;
  63.     return;
  64. }
  65.  
  66. void precal()
  67. {
  68.     ll i,j,ncount;
  69.     for(i=2;i<MAXN;i++){
  70.         if(val[i]==0)val[i]=1;
  71.         val[i]=((val[i-1]%MOD)*(val[i]%MOD))%MOD;
  72.     }
  73. }
  74.  
  75. int main()
  76. {
  77.     ll t,test=0,n;
  78.     sieve();
  79.     precal();
  80.     cin>>t;
  81.     while(t--){
  82.         cin>>n;
  83.         cout<<"Case "<<++test<<": "<<val[n]<<endl;
  84.     }
  85.     return 0;
  86. }
  87.  
Success #stdin #stdout 1.2s 893952KB
comments (?)
stdin
copy 
1
2
stdout
copy 
Case 1: 2
https://ideone.com/oWwCL2
language:
C++ (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!