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


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

hide comments
2013-04-15 15:57:39 (Tjandra Satria Gunawan)(曾毅昆)
my best time is 0.13s in C++
rank #12 of 5253 user ;-)
~0.09s=precomputation time
~0.04s=input/output time
2013-04-15 15:57:39 Francky
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
2013-04-15 15:57:39 xyb
Just replace cin/cout with scanf/printf, got AC.
2013-04-15 15:57:39 rb
finally got AC!!!!!!!
2013-04-15 15:57:39 useless
Super easy..move to tutorials..
2013-04-15 15:57:39 srishti goel
my code is working in ideone bt showing a run time error here..
what should i do??
2013-04-15 15:57:39 eliminator
@secret22
sqrt is the key ... ;)
2013-04-15 15:57:39 secret22
tle... :( help me.......
2013-04-15 15:57:39 Shubham
O(t+m*m)(m is maxsize here i.e. 500000 and t,test cases) is faster than O(t*sqrt(n)). why is it so?

Got the glitch :)
it's not m*m but (m/2+m/3+m/4+m/5+....)

Last edit: 2012-08-12 18:20:58
2013-04-15 15:57:39 nikoo28
imp test case:
input =1
output =0

input =500000
output =730453

and 3 sec is too much of a time limit
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.