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
Abhinandan Agarwal:
2015-02-23 00:12:32
Quite a fun , it was ... from .53 to 0.0 .. |
|
Harry Mathis:
2014-07-12 11:14:19
The input / output examples above show new lines. That coasts me firstable an nzec-error! Last edit: 2014-07-12 11:40:25 |
|
Mukund Kumar:
2013-12-29 10:30:38
Great problem...costed me 3 tle to realize what was needed... ;) |
|
Aniket Kumar:
2013-12-29 10:30:38
good question... :) |
|
wisfaq:
2013-12-29 10:30:38
Can this problem be made available for all languages?
|
|
Ouditchya Sinha:
2013-12-29 10:30:38
Awesome problem... Costed me 2 TLE's to realise what the problem setter wanted. :) |
|
god_father:
2013-12-29 10:30:38
awesome problem .... |
|
Vikas Kushwaha:
2013-12-29 10:30:38
nice way to frame question :) |
|
Nnavneetsinha:
2013-12-29 10:30:38
Awesome problem |
|
Jignesh:
2013-12-29 10:30:38
wasted time finding patterns in output.. when there is such a straight forward simple solution, nice problem :) Last edit: 2012-12-09 06:25:55 |
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 |