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
des1997:
20180623 11:50:33
ran in 3.02 seconds:) 

karthik1997:
20171228 13:39:05
Can't go below 2s . :( 

kmkhan_014:
20171221 16:55:26
this is extremel !!! AC in 15s 

mastik5h_1998:
20170623 07:40:49
very annoying question.......


oualiamine:
20170320 22:12:50
what does 1e16 means?


kira28:
20170104 21:13:04
Finally !!!!


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 
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 