DIVSUM - Divisor Summation


Given a natural number n (1 ≤ n ≤ 500000), please output the summation of all its proper divisors.

Definition: A proper divisor of a natural number is the divisor that is strictly less than the number.

e.g. number 20 has 5 proper divisors: 1, 2, 4, 5, 10, and the divisor summation is: 1 + 2 + 4 + 5 + 10 = 22.

Input

An integer stating the number of test cases (equal to about 200000), and that many lines follow, each containing one integer between 1 and 500000 inclusive.

Output

One integer each line: the divisor summation of the integer given respectively.

Example

Sample Input:
3
2
10
20

Sample Output:
1
8
22

Warning: large Input/Output data, be careful with certain languages


hide comments
@looser@: 2013-04-15 15:57:39

I love to hate TLE ::

Ouditchya Sinha: 2013-04-15 15:57:39

finally AC :)

Vitalis Salis: 2013-04-15 15:57:39

Value for 1 is 0. Don't forget to take a special case about that ;)

nbcool: 2013-04-15 15:57:39

My solution is also giving TLE there is a just order n loop

Rounak Patni: 2013-04-15 15:57:39

TLE help plz

o.O: 2013-04-15 15:57:39

TLE...
plz someone help....

Francky: 2013-04-15 15:57:39

@tjandra, no you're #10, Miki Maric gave a wrong code, those two submissions are making some trouble in this rank list. I think they should be hidden.

(Tjandra Satria Gunawan)(曾毅昆): 2013-04-15 15:57:39

my best time is 0.13s in C++
rank #12 of 5253 user ;-)
~0.09s=precomputation time
~0.04s=input/output time

Francky: 2013-04-15 15:57:39

I've work many times on this problem since almost a year. This is THE problem that push me to learn C. I haven't the fastest chrono, but I'm very happy today with this one. \o/
Edit : I reach the point where IO take most of time : only read/cast input and write whatever number take me between 0.05 and 0.08s like my fastest AC. So, I'll come back if I found faster IO.

Last edit: 2012-11-29 23:48:32
xyb: 2013-04-15 15:57:39

Just replace cin/cout with scanf/printf, got AC.


Added by:Neal Zane
Date:2004-06-10
Time limit:3s
Source limit:5000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Neal Zane