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

why would i get runtime error??

vinodh reddy velemineti: 2013-04-15 15:57:39

can any ne help me how to ramove it

vinodh reddy velemineti: 2013-04-15 15:57:39

i am getting time limit exceede error

vishal chaudhary: 2013-04-15 15:57:39

@Anup..its because 'scanf' and 'printf' in 'C' are 2-3 times faster than 'cin' and 'cout' in c++ ...thereby reducing the run time and increasing its efficiency which is important for the spoj problems to be accepted...:)

krishna_0507: 2013-04-15 15:57:39

i din't understand how is this spoj compiler working.....when m doing this ques in c++ with an algo it shows me time-limit exceeded .......bt after 3 hrs when i replaced that same file in c replacing just cout's and cin's with printf's and scanf's it accepts my solution .....without any prior change to my rest of the code......can anyone plzzz tell me the reason why is this happening???????thanks in advance...

napster: 2013-04-15 15:57:39

finally...:)

its in the code !: 2013-04-15 15:57:39

what should i do to avoid 'time limit exceeded'?

Alexey: 2013-04-15 15:57:39

<snip>
Look at this code. It was getting TLE and RE all the time. How?? It's obviously WA should be, but TLE or RE? May i don't know something about F#? Please, explain the ones who knows

Last edit: 2023-03-08 17:58:23
sahil: 2013-04-15 15:57:39

what is the value for 1 ?

Darky: 2013-04-15 15:57:39

Don't forget to take long for n. Cost me many submissions just because of that.


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