Sunday, February 3, 2019

[Spoj] DCEPCA03 - Totient Extreme

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : DCEPCA03 - Totient Extreme
Source            : Spoj
Category          : Number Theory
Algorithm         : Eular Totient Function
Verdict           : Accepted

  1. #include "bits/stdc++.h"  
  2.   
  3. using namespace std;  
  4.   
  5. #define ll          long long int  
  6.   
  7. static const int maxn = 1e4 + 5;  
  8.   
  9. int phi[maxn];  
  10.   
  11. void eularPhi()  
  12. {  
  13.       for (int i = 1; i < maxn; i++) phi[i] = i;  
  14.       for (int p = 2; p < maxn; p++)  
  15.       {  
  16.             if (phi[p] == p)  
  17.             {  
  18.                   for (int k = p; k < maxn; k += p)  
  19.                   {  
  20.                         phi[k] -= phi[k]/p;  
  21.                   }  
  22.             }  
  23.       }  
  24. }  
  25.   
  26. int phiSum[maxn];  
  27.   
  28. void func()  
  29. {  
  30.       phiSum[1] = phi[1];  
  31.       for (int i = 2; i < maxn; i++)  
  32.       {  
  33.             phiSum[i] += phi[i] + phiSum[i-1];  
  34.       }  
  35. }  
  36.   
  37. ll Res(int n)  
  38. {  
  39.       ll res = 0;  
  40.       ll mul = phiSum[n];  
  41.       for (int i = 1; i <= n; i++) res += phi[i] * mul;  
  42.       return res;  
  43. }  
  44.   
  45. int main()  
  46. {  
  47.       eularPhi();  
  48.       func();  
  49.   
  50.       int tc;  
  51.       cin >> tc;  
  52.       for (int tcase=1; tcase<=tc; tcase++)  
  53.       {  
  54.             int n;  
  55.             cin >> n;  
  56.             ll res = Res(n);  
  57.             cout << res << endl;  
  58.       }  
  59. }  

No comments:

Post a Comment

Note: Only a member of this blog may post a comment.