fork(1) download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int a[10000005];
  4. void sieve()
  5. {
  6.     int n=10000000,i,j;
  7.     for(i=4;i<=n;i+=2)
  8.             a[i]=1;
  9.     for(i=3;i<=sqrt(n);i+=2)
  10.     {
  11.         if(a[i]==0)
  12.         {
  13.             for(j=i*i;j<=n;j+=i)
  14.                 a[j]=1;
  15.         }
  16.     }
  17. }
  18. int phi(int n)
  19. {
  20.     int result,i,j,k;
  21.     result=n;
  22.     for(i=2;i<=sqrt(n);i++)
  23.     {
  24.         if(n%i==0)
  25.         {
  26.             while(n%i==0)
  27.                 n=n/i;
  28.             result-=result/i;
  29.         }
  30.     }
  31.     if(n>1)
  32.         result-=result/n;
  33.     return result;
  34. }
  35. int main()
  36. {
  37.      long long int t,m,n,z,k=0,x,y,i,j,c,d;
  38.      stack<int>s;
  39.      sieve();
  40.      for(i=2;i<=10000000;i++)
  41.      {
  42.          if(a[i]==0)
  43.             a[i]=a[i-1]+1;
  44.          else
  45.             a[i]=a[i-1];
  46.      }
  47.      cin>>t;
  48.      while(t--)
  49.      {
  50.         cin>>n;
  51.         x=phi(n);
  52.         y=max(k,a[n]-x);
  53.         m=1;
  54.         if(y>=1)
  55.             m=x;
  56.         for(i=2;i<=y;i++)
  57.         {
  58.             j=i;
  59.             c=1;
  60.             while(j)
  61.             {
  62.                 s.push(j);
  63.                 if(j%2==0)
  64.                     j/=2;
  65.                 else
  66.                     j--;
  67.             }
  68.             while(!s.empty())
  69.             {
  70.                 z=s.top();
  71.                 s.pop();
  72.                 if(z%2==1)
  73.                     c=((c%1000000007)*(m%1000000007))%1000000007;
  74.                 else
  75.                     c=((c%1000000007)*(c%1000000007))%1000000007;
  76.             }
  77.             m=c%1000000007;
  78.         }
  79.         cout<<m<<endl;
  80.      }
  81. }
Runtime error #stdin #stdout 0.16s 42444KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/Xflrxi
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!