[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. }