All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Given a positive integer n, Chef has asked you to calculate the following sum in the most efficient way:
Here gcd(a,b) means greatest common divisor of two integers a and b.
The first line of input contains an integer T denoting the number of test cases. The description of T test cases follows.The only line describing each test case contains a single integer n, given to you by Chef.
Please note that input can be very large. So it's recommended to use fast IO methods.
For each test case, output a single line containing one integer: answer to Chef's query.
Constraints and Subtasks
- 1 ≤ T ≤ 106
- 1 ≤ n ≤ 107
Subtask1(10 points): 1 ≤ sum of n over all testcases ≤ 107, TL=1.5s
Subtask2(20 points): 1 ≤ n ≤ 104,
Subtask3(70 points): No additional constraints,
Input: 5 1 2 3 4 5 Output: 1 3 7 11 21
|Tags||easy, factorization, kaizer, nov15|
|Time Limit:||1 - 1.5 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.