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
supratik101: 2016-02-10 18:10:03

How to wite test case in program?

Abhishek Kumar Singh: 2016-02-01 08:20:43

For those who are getting WA, take care of the square no.'s.That is no's such as 16.

Nallagatla Manikanta: 2016-01-19 16:25:07

For n=1, answer should be 0. Cost me 1 WA!! Got AC finally!

shohjahon: 2016-01-17 19:09:07

Hello everybody, Could anybody explain me why runtime error is occuring in my judge, (I have tested the program on my c++ compiler , the answer is being correcly for every case also 1)

kiner_shah: 2016-01-02 12:26:58

For n=1, answer should be 0. Cost me 1 WA!! Got AC finally!

duongpbc: 2015-12-27 00:43:39

Can anyone give me a test with O(log n)?

burgund: 2015-12-17 14:32:11

C# TLE

Archil K Srivastava: 2015-12-17 08:49:41

I don't know why i am getting wrong answer. I expected a TLE but definitely not a WA.
Submission id 15882395
Edit: AC :) (I am dumb)

Last edit: 2015-12-17 19:13:22
lakshjain: 2015-12-05 17:37:33

@Anchrondite answer for input 1 must be zero its because we need to consider proper divisors that are less than the given number so for number only divisor is 1 but it is not a proper divisor as it is not less than 1 i hope u got.

vishesh9494: 2015-12-04 08:03:18

hi...can anyone please give me some test cases as i am getting wrong answer the whole way even though in my testing on my laptop i am getting right answers...please help...thank you in advance


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