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

finally got AC!!!!!!!

useless: 2013-04-15 15:57:39

Super easy..move to tutorials..

srishti goel: 2013-04-15 15:57:39

my code is working in ideone bt showing a run time error here..
what should i do??

eliminator: 2013-04-15 15:57:39

@secret22
sqrt is the key ... ;)

secret22: 2013-04-15 15:57:39

tle... :( help me.......

Shubham: 2013-04-15 15:57:39

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

imp test case:
input =1
output =0

input =500000
output =730453

and 3 sec is too much of a time limit

Monkey D. Luffy : 2013-04-15 15:57:39

For extra efficiency, remember that divisors come in pairs. For example, if 2 is a divisor of 20 then so is 20/2 = 10.

StupidGuy: 2013-04-15 15:57:39

Finally ACC..But still bad Time...:(

Those with TLE, try printf scanf...it really improves time.
Also sqrt() is faster than i*i

Last edit: 2012-07-08 12:23:53
Kartik Godawat: 2013-04-15 15:57:39

Please help. Tried every possible way for removing TLE. Computation done in <500ms for all inputs at local machine(every no <500000). Using Java BufferedReader.


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