DCEPCA03 - Totient Extreme
Given the value of N, you will have to find the value of H. The meaning of H is given in the following code:
H=0;
For (i=1; i<=n; i++) {
For (j=1; j<=n; j++) {
H = H + totient(i) * totient(j);
}
}
Totient or phi function, φ(n) is an arithmetic function that counts the number of positive integers less than or equal to n that are relatively prime to n. That is, if n is a positive integer, then φ(n) is the number of integers k in the range 1 ≤ k ≤ n for which gcd(n, k) = 1
Constraints
0 < T <= 50
0 < N <= 10^4
Input
The first line contains T, the number of test cases. It is followed by T lines each containing a number N .
Output
For each line of input produce one line of output. This line contains the value of H for the corresponding N.
Example
Input: 2 3 10 Output: 16 1024
hide comments
gautam:
2016-10-10 20:47:55
easy one . |
|
Min_25:
2016-07-25 14:00:49
@square1001
|
|
square1001:
2016-07-25 13:51:36
It's a nice problem.
|
|
yeasintamim:
2016-06-23 20:21:23
why TLE ??
|
|
surya2196:
2016-05-21 12:56:25
lolypop question |
|
darkhire21:
2016-01-04 08:53:22
Nice problem ...!! |
|
dragonemperor:
2015-10-19 12:17:22
AC in first go :) |
|
ASHUTOSH DWIVEDI:
2015-09-19 00:07:05
O(n*(sqrt(n)/log(sqrt(n))*log(n))) is enough.... Last edit: 2015-09-21 20:03:53 |
|
:.Mohib.::
2015-07-02 17:30:39
Really nice que!! |
|
manu nigotia:
2015-06-21 21:59:55
Failed to realize, it was this easy a problem. AC after 5 TLEs. |
Added by: | dce coders |
Date: | 2012-12-05 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | C CSHARP C++ 4.3.2 CPP C99 HASK JAVA PAS-GPC PAS-FPC PYTHON PYTHON3 PY_NBC |
Resource: | Own Problem |