LCM SumProblem code: SNON02 |
Given n, calculate the sum LCM(1,n) + LCM(2,n) + .. + LCM(n,n), where LCM(i,n) denotes the Least Common Multiple of the integers i and n.
Input :
The first line contains T the number of test cases. Each of the next T lines contain an integer n.
Output :
Output T lines, one for each test case, containing the required sum.
Sample Input :
3 1 2 5
Sample Output :
1 4 55
Constraints :
1 <= T <= 300000
1 <= n <= 1000000
| Author: | fctrl |
| Date Added: | 28-12-2009 |
| Time Limit: | 6 sec |
| Source Limit: | 10000 Bytes |
| Languages: | ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TEXT, WSPC |
Comments

Fetching successful submissions

Will answer fit in a signed
Will answer fit in a signed 64-bit integer?
Yeah, it will
Yeah, it will
Time limit is very strict.
Time limit is very strict. :-|