SHARE
TWEET

Untitled

a guest Apr 21st, 2019 91 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. /// Typedef
  6. typedef long long           ll;
  7. typedef unsigned long       ul;
  8. typedef unsigned long long  ull;
  9. typedef vector<int>         vi;
  10. typedef vector<vi>          vvi;
  11. typedef vector<ll>          vll;
  12. typedef pair<int,int>       pii;
  13. typedef pair<ll,ll>         pll;
  14. typedef vector< pii >       vii;
  15.  
  16. #define pb                  push_back
  17. #define ppb                 pop_back
  18. #define MP                  make_pair
  19. #define ff                  first
  20. #define ss                  second
  21. #define sf                  scanf
  22. #define pf                  printf
  23. #define SQR(x)              ((x)*(x))
  24. #define loop(i, y)          for(int i=0; i<int(y); i++)
  25. #define FOR(i, x, y)        for(int i=int(x); i<=int(y); i++)
  26. #define ROF(i, x, y)        for(int i=int(x); i>=int(y); i--)
  27. #define ALL(c)              c.begin(), c.end()
  28. #define SZ(c)               int(c.size())
  29. #define CLR(x, y)           memset(x, y, sizeof(x))
  30. #define READ(f)             freopen(f, "r", stdin)
  31. #define WRITE(f)            freopen(f, "w", stdout)
  32. #define FastIO              ios_base::sync_with_stdio(false)
  33. #define tr(it, container)   for(auto it = container.begin(); it != container.end(); it++)
  34. #define sci(x)              scanf("%d", &x)
  35. #define scii(x, y)          scanf("%d %d", &x, &y)
  36. #define sciii(x, y, z)      scanf("%d %d %d", &x, &y, &z)
  37. #define scl(x)              scanf("%lld", &x)
  38. #define scll(x, y)          scanf("%lld %lld", &x, &y)
  39. #define sclll(x, y, z)      scanf("%lld %lld %lld", &x, &y, &z)
  40. #define bitCheck(N,in)      ((bool)(N&(1<<(in))))
  41. #define bitOff(N,in)        (N&(~(1LL<<(in))))
  42. #define bitOn(N,in)         (N|(1LL<<(in)))
  43. #define bitFlip(a,k)        (a^(1LL<<(k)))
  44. #define unq(v)              sort(all(v)), (v).erase(unique(all(v)),v.end())
  45. #define common(a,b)         sort(all(a)), sort(all(b)), a.erase(set_intersection(all(a),all(b),a.begin()),a.end())
  46. #define uncommon(a,b)       sort(all(a)), sort(all(b)), a.erase(set_symmetric_difference(all(a),all(b),a.begin()),a.end())
  47. #define dbg(x)              cout<<#x<<" = "<<x<<endl;
  48.  
  49. template <class T> inline T bigMod(T p,T e,T M){ ll ret = 1; for(; e > 0; e >>= 1){ if(e & 1) ret = (ret * p) % M; p = (p * p) % M; } return (T) ret;}
  50. template <class T> inline T modInverse(T a,T M){return bigMod(a,M-2,M);}
  51. template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
  52. template <class T> inline T lcm(T a,T b) {a=abs(a);b=abs(b); return (a/gcd(a,b))*b;}
  53. template <class T> inline string int2String(T a){ostringstream str; str<<a; return str.str();}
  54. const int dr[] = { 0,  1,  0, -1,        -1,  1,  1, -1,     -2, -2,  2,  2, -1, -1,  1,  1};
  55. const int dc[] = { 1,  0, -1,  0,         1,  1, -1, -1,     -1,  1, -1,  1, -2,  2, -2,  2};
  56.  
  57.  
  58.  
  59. /*primes in range 1 - n
  60. 1 - 100(1e2) -> 25 primes
  61. 1 - 1000(1e3) -> 168 primes
  62. 1 - 10000(1e4) -> 1229 primes
  63. 1 - 100000(1e5) -> 9592 primes
  64. 1 - 1000000(1e6) -> 78498 primes
  65. 1 - 10000000(1e7) -> 664579 primes
  66. large primes ->
  67. 104729 1299709 15485863 179424673 2147483647 32416190071 112272535095293 48112959837082048697
  68. */
  69.  
  70.  
  71. #define for1(a,b) for(ll i=a; i<b; i++)
  72. #define rev(v) reverse(v.begin(),v.end())
  73. #define srt(v) sort(v.begin(),v.end())
  74. #define grtsrt(v) sort(v.begin(),v.end(),greater<ll>())
  75.  
  76.  
  77. /// Constants
  78. #define mx                 10000007
  79. #define MOD                 1000000009
  80. #define base                1000000007
  81. #define eps                 1e-9
  82. #define INF                 1llu<<61    // 2,305,843,009,213,693,952
  83. #define inf                 1<<29       // 536,870,912
  84. #define PI                  acos(-1.0)  // 3.1415926535897932
  85.  
  86.  
  87. char allNumber_1_To_1000[3000] = "1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000";
  88.  
  89. /************ Start my personal Library ************/
  90. // Square number count in 2 number range (3 - 10)--> 2
  91.  
  92. #define Square_number_count_in_2_rang(n) for(ll i=0; i<n; i++){ scl2(a,b); ck = sqrt(a-1); dk = sqrt(b); cout<<dk-ck<<endl; }
  93.  
  94. int sum[mx];
  95. ll max(ll a, ll b){  return (a>b) ? a : b; }
  96.  
  97. ll knapsack(ll cap,ll wt[],ll val[],ll item){ if(cap==0 || item == 0) return 0; if(wt[item-1]>cap) return knapsack(cap, wt, val, item-1);
  98.    else return max(val[item-1]+ knapsack(cap-wt[item-1], wt, val, item-1), knapsack(cap, wt, val, item-1) ); }
  99.  
  100. ll totalLearYearCount(ll year){ ll check4 = year/4; ll check100 = year/100; ll check400 = year/400; return (check4 + check400) - check100; }
  101.  
  102. ll checkTwoSquaresOrNotTwoSquares(ll n ){ ll a = sqrt(n),ck=0,i=0,j=0; while(a > 0){ if(i*i > n){ cout<<"No"<<endl; break; } else if(a*a + i*i == n){
  103.    cout<<"Yes"<<endl; break; } else if(a*a + i*i < n){ i++; } else a--; } }
  104.  
  105. bool checkPrime(int n) { int i; if(n<=1)return false; for(i=2;i*i<=n;i++){ if(n%i==0)return false; } return true; }
  106. void primeSaveinArray() { sum[0] = sum[1]=0; for(int i=2; i<=mx; i++){ sum[i] = sum[i-1]; if(checkPrime(i)){ sum[i]++; } } }
  107.  
  108. ll revNumber(ll n) { ll b=0; while(n!=0){ b = b*10 + n%10; n/=10; } return b; }
  109.  
  110. ll learYearCheck(ll year) { if(year%4!=0) return 0; else if(year%100!=0) return 1; else if(year%400!=0) return 0; else return 1; }
  111.  
  112. ll countDevisior(ll n) { ll ck=0; for(ll i=1; i*i<=n; i++){ if(n%i==0){ ck++; if(i!=n/i) ck++; } } return ck; }
  113.  
  114. ll primeFactorsCount(ll n){ ll gf =0;  while (n%2 == 0) { gf++; n = n/2; } for (ll i = 3; i <= sqrt(n); i = i+2) { while (n%i == 0) { gf++;  n = n/i; } } if (n > 2){ gf++; } return gf; }
  115.  
  116. ll factorial(ll n) { if(n == 1) return 1; return n*factorial(n-1); }
  117.  
  118. ll binarySearch(ll high, ll sV, ll arr[]) { ll low = 0; while(low<=high){ ll mid = (high+low)/2; if(sV == arr[mid]) return mid+1; else if(sV > arr[mid]) low = mid+1; else high = mid-1; } return -1; }
  119.  
  120.  
  121. /************ Start my main method code ************/
  122.  
  123. char ar[26] = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
  124.  
  125. bool com(pair<string ,string> a , pair<string, string> b ){
  126.      if(a.second==b.second) return a.first < b.first;
  127.      return a.second < b.second; }  /// kom theke beshi sort ///return p.first > q.first; /// beshi theke kom sort
  128.  
  129.  
  130. ll checkprime[mx];
  131. vector<ll>prime;
  132.  
  133. void sieve(){    ll n,i,j;    for(i=4; i<mx; i+=2) checkprime[i] = 1;    for(i=3; i*i<=mx; i+=2){        if(checkprime[i]==0){            for(j=i*i; j<mx; j+=(i+i))                checkprime[j] = 1;        }    }    for(i=2; i<mx; i++) if(!checkprime[i]) prime.push_back(i);}
  134.  
  135.  
  136. int computeTotient(int n)
  137. {
  138.     double prod = n;
  139.         for (int i = 0; i < prime.size() && prime[i] <= n; i++) {
  140.             if (n % prime[i] == 0) {
  141.                 do{
  142.                     n /= prime[i];
  143.                 }
  144.                 while (n % prime[i] == 0);
  145.                 prod *= (1.0 - 1.0 / prime[i]);
  146.             }
  147.         }
  148.         if (n > 1)
  149.             prod *= (1.0 - 1.0 / n);
  150.         return (int)prod;
  151. }
  152.  
  153. int main(){
  154.  
  155.     //READ("input.txt");
  156.     //WRITE("output.txt");
  157.     int n;
  158.     sieve();
  159.     while(sci(n) && n){
  160.         int cnt=computeTotient(n);
  161.         cout<<cnt<<endl;
  162.     }
  163.     return 0;
  164. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top