fork download
copy 
  1. //Bismillahir Rahmanir Rahim
  2. /******Harun Or Rashid******/
  3. /***********Template Starts Here***********/
  4. #include<iostream>
  5. #include<cstdio>
  6. #include<cstring>
  7. #include<cmath>
  8. #include<cctype>
  9. #include<cstdlib>
  10. #include<cassert>
  11. #include<string>
  12. #include<vector>
  13. #include<set>
  14. #include<stack>
  15. #include<queue>
  16. #include<map>
  17. #include<algorithm>
  18. using namespace std;
  19.  
  20. #define MEM(a,b) memset(a,b,sizeof(a))
  21. #define CLR(a) memset(a,0,sizeof(a))
  22. #define MAX(a,b) ((a)>(b)?(a):(b))
  23. #define MIN(a,b) ((a)>(b)?(b):(a))
  24. #define ABS(a) ((a)>0? (a):(-(a)))
  25. #define SQ(a) ((a)*(a))
  26. #define SZ(a) (int)a.size()
  27. #define FORN(i,n) for(i=1;i<=n;i++)
  28. #define FORAB(i,a,b) for(i=a;i<=b;i++)
  29. #define ALL(V) V.begin(),V.end()
  30. #define pb(a) push_back(a)
  31. #define pr(a) cout<<a<<endl
  32. #define SQR(a) ((a)*(a))
  33. #define pf printf
  34. #define sf scanf
  35. #define swap(a,b) (a ^= b, b ^= a, a ^= b)
  36. #define PI acos(-1)
  37. #define x first
  38. #define y second
  39. #define eps 1e-7
  40.  
  41. typedef int D;
  42. typedef long long int LLD;
  43. typedef unsigned long long int LLU;
  44. typedef vector<D> VI;
  45. typedef set<D> SI;
  46. typedef vector<D>::iterator Viti;
  47.  
  48. /***********Template Ends Here***********/
  49. int phi(int n)
  50. {
  51.     if(n<3) return 1;
  52.     int result=n;
  53.     if(n%2==0)
  54.     {
  55.         result-=result/2;
  56.         while(n%2==0) n/=2;
  57.     }
  58.     for(int i=3; i*i<=n; i+=2)
  59.     {
  60.         if(n%i==0)
  61.         {
  62.             result-=result/i;
  63.             while(n%i==0) n/=i;
  64.         }
  65.     }
  66.     if(n>1) result-=result/n;
  67.     return result;
  68. }
  69. int main()
  70. {
  71.     int T,n;
  72.     cin>>T;
  73.     while(T--)
  74.     {
  75.         cin>>n;
  76.         cout<<phi(n)<<endl;
  77.     }
  78.     return 0;
  79. }
  80.  
  81.  
Success #stdin #stdout 0s 3300KB
comments (?)
stdin
copy 
5
1
2
3
4
5
stdout
copy 
1
1
2
2
4
https://ideone.com/cG1KKO
language:
C++ (gcc 8.3)
created:
10 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!