Euler’s Phi Function:

Concept:  

Shoshikkha 

প্রোগ্রামিং পাতা 

topH 

 Type 01:

( যখন একসাথে অনেক গুলোর জন্য বের করতে হবে।)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44

#include<bits/stdc++.h> using namespace std; #define MAX 2000100 typedef long long ll; ll phi[MAX]; void seivePHI(){ ll i,j; for(i = 2; i < MAX; i++){ if(phi[i] == 0){ phi[i] = i - 1; for(j = i*2; j < MAX; j += i){ if(phi[j] == 0)phi[j] = j; phi[j] /= i; phi[j] *= (i-1); } } } } int main() { /* #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #endif double start_time = clock();*/ int t; seivePHI(); cin >> t; for(int cs = 1; cs <= t; cs++){ int n; cin >> n; cout << "Phi("<<n<<") = "<<phi[n]<<endl; } /*double end_time = clock(); printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000); */ return 0; }

Type 02:

( যখন  একটা সংখ্যার জন্য বের করতে হবে।)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61

#include<bits/stdc++.h> using namespace std; #define MAX 2000100 typedef long long ll; ll po(ll x, ll y){ ll ans = 1; while(y--) ans *= x; return ans; } ll prime(ll a) { for(ll i = 1; i*i <= a; i++){ if(a%i == 0)return 1; } return 0; } ll phi(ll n) { ll i,mul = 1, holder, fre = 0; if(prime(n) == 0) mul = n - 1; else{ for(i = 2; i*i <= n; i++){ if(n%i == 0){ while(n%i == 0){ n = n/i; holder = i; fre++; } mul *= (po(holder, fre-1)*(holder - 1)); fre = 0; } } if(n != 1){ mul *= (n-1); } } return mul; } int main() { // #ifndef ONLINE_JUDGE //freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); // #endif //double start_time = clock(); ll n; cin >> n; cout << "Phi("<<n<<") = "<<phi(n)<<endl; //double end_time = clock(); //printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000); return 0; }

  Problems: D. Same GCDs   Solution

Share: