Author : Dipu Kumar Mohanto
CSE, Batch - 6
BRUR.
Problem Statement : DCEPCA03 - Totient Extreme
Source : Spoj
Category : Number Theory
Algorithm : Eular Totient Function
Verdict : Accepted
- #include "bits/stdc++.h"
-
- using namespace std;
-
- #define ll long long int
-
- static const int maxn = 1e4 + 5;
-
- int phi[maxn];
-
- void eularPhi()
- {
- for (int i = 1; i < maxn; i++) phi[i] = i;
- for (int p = 2; p < maxn; p++)
- {
- if (phi[p] == p)
- {
- for (int k = p; k < maxn; k += p)
- {
- phi[k] -= phi[k]/p;
- }
- }
- }
- }
-
- int phiSum[maxn];
-
- void func()
- {
- phiSum[1] = phi[1];
- for (int i = 2; i < maxn; i++)
- {
- phiSum[i] += phi[i] + phiSum[i-1];
- }
- }
-
- ll Res(int n)
- {
- ll res = 0;
- ll mul = phiSum[n];
- for (int i = 1; i <= n; i++) res += phi[i] * mul;
- return res;
- }
-
- int main()
- {
- eularPhi();
- func();
-
- int tc;
- cin >> tc;
- for (int tcase=1; tcase<=tc; tcase++)
- {
- int n;
- cin >> n;
- ll res = Res(n);
- cout << res << endl;
- }
- }
No comments:
Post a Comment
Note: Only a member of this blog may post a comment.