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
2015-06-30 23:16:35
https://www.spoj.com/forum/viewtopic.php?f=3&t=22858&sid=23e7c2dbfa3b9f93bef8360b2ca35676
2015-06-21 15:13:15
i used just 2 loops my code is too small and it gets time limit ......this online judge get every thin time limit -__- i am using c++ btw.
2015-04-14 06:39:25 BRAIN
if n = 1 then print "0"
2015-04-12 07:48:38 Tan
I am using Java. I thought of taking input in an array. But I need to allocate space for 20000 numbers in array at time of declaration. How do I get past this memory problem?
2015-03-26 18:25:33 Eugene Che
The most apparent solution to me was generating a lookup table for all the test cases. I wonder if the root(n) solution is fast enough.
2015-03-25 06:53:56 jonmadison
nodejs is a no go (fastest i got was 42 secs), same algorithm in C results in a fast enough run. also Marcin is right. testcase includes 0, contrary to the task

Last edit: 2015-03-25 07:08:24
2015-03-24 20:44:21 Marcin Wawerka
The testcases are not consistent with the task, there is a testcase checking the output for 0, which shouldn't happen.
2015-03-20 14:07:16 Hot-Shot
one day reckless coding will sink my algorithmic ship..... :P
AC in 2nd go...curse me god
2015-03-07 14:54:20 Zoli
I got TLE for optimal solution in Python 3.4, any suggestions?

(Francky) => There's several PY3.4 AC, so your solution isn't optimal.

Last edit: 2015-03-07 15:15:52
2015-03-01 13:36:41 Otaku Jome
I have spent so much time optimising, but it still says it's too slow. There seems to be no fast enough solution.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.