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
Michael Yockey: 2013-04-15 15:57:39

It would seem that, since there are zero ruby solutions, that the time limit is much too short for the amount of IO required.

Pavel: 2013-04-15 15:57:39

cin and cout are slow, use scanf and printf instead

Last edit: 2011-10-24 02:33:22
avinash choudhary: 2013-04-15 15:57:39

for 1 its 0..mind it...:)

Trimbitas Petru: 2013-04-15 15:57:39

I think the time limit is to low. The same algorithm using streams gets tle.

Santiago Palacio: 2013-04-15 15:57:39

@Vasanth.N there are 2 options, 1 your program does not know when to halt and keeps looping, or 2 (most likely) the algorithm is not fast enough and should be changed, also there could be some I/O optimization needed, but in this problem it's unlikely.

Vasanth.N: 2013-04-15 15:57:39

why time limit exceeded?????

Last edit: 2011-06-22 06:54:34
Santiago Palacio: 2013-04-15 15:57:39

@ alg0: an O(sqrt(n)) algorithm should pass, mine did, look for I/O optimizations.

Last edit: 2011-06-13 06:07:00
SD: 2013-04-15 15:57:39

Why TLE??? Although i m generating the array for sum only one time???

Ocean Blue: 2013-04-15 15:57:39

do you have to use buffers to avoid TLE??

alg0_seekar: 2013-04-15 15:57:39

hi guys i m using O(sqrt(n) algorithm still getting TLE..can any one suggest what optimization still i needed..??


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