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 22warning: a naive algorithm may not run in time.
hide comments
square1001:
20160726 06:21:28
I got 4.90 sec!


nightwolf_9197:
20160219 13:15:56
Bin Jin please check my submission as it takes <2seconds on ideone.com but here it shows tle


ashish kumar:
20151226 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:
20150722 06:00:51
Done Last edit: 20160929 13:54:35 

[Lakshman]:
20150713 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.::
20150713 16:53:24
I got AC in 11s :( .... Can somebody give idea about optimization?? 

Ouditchya Sinha:
20130623 20:58:07
Finally AC!!! A very Challenging Problem! Look out for overflows & it is sum of "proper" divisors. 

Nic Roets:
20110717 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:  20070829 
Time limit:  18.17s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: CPP 
Resource:  own problem 