DIVSUM2 - Divisor Summation (Hard)


Given a natural number n (1 <= n <= 1e16), 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 500), and that many lines follow, each containing one integer between 1 and 1e16 inclusive.

Output

One integer each line: the divisor summation of the integer given respectively.

Example

Input:
3
2
10
20

Output:
1
8
22
warning: a naive algorithm may not run in time.

hide comments
square1001: 2016-07-26 06:21:28

I got 4.90 sec!
The time complexity is O(n^0.5 log n + qπ(n^0.5)).

nightwolf_9197: 2016-02-19 13:15:56

Bin Jin please check my submission as it takes <2seconds on ideone.com but here it shows tle

ashish kumar: 2015-12-26 15:24:25

I am using optimized sieve with miller rabin test to check for prime and a sqrt time divisor function after all my time is about 4.5 secs. But @Lakshman and some other they got exceptionally less time . How it is possible?

Bhuvnesh Jain: 2015-07-22 06:00:51

Done

Last edit: 2016-09-29 13:54:35
[Lakshman]: 2015-07-13 18:10:50

@Mohib if you are using seive with trial division you can do it in less than 4s with optimized seive and divisor function. If you want more faster algorithm go for Pollard Rho.

:.Mohib.:: 2015-07-13 16:53:24

I got AC in 11s :( .... Can somebody give idea about optimization??

Ouditchya Sinha: 2013-06-23 20:58:07

Finally AC!!! A very Challenging Problem! Look out for overflows & it is sum of "proper" divisors.

Nic Roets: 2011-07-17 03:56:49

Just to make it clear: The 500 test numbers were not randomly chosen. They were chosen to make the run time as long as possible.


Added by:Bin Jin
Date:2007-08-29
Time limit:18.17s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: CPP
Resource:own problem