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
indrajitsadh:
20210427 20:38:47
Look at languages ....?


rupok_03:
20201019 18:30:10
use div_sum = 1LL & bitset for sieve


jagonmoy:
20200713 13:26:37
Use bitwise sieve to store the primes up to 10^8 then for each query just use the simple sum of divisors algorithm .


jainapoorv094:
20200611 18:53:50
is the ans fit in long long


nurbijoy:
20200518 20:06:08
check out my code. can't get AC. TLE


arman____:
20200331 21:54:26
got acc in simple SOD...just range and time limit big.. 

myner:
20191207 12:59:38
can it be that the test cases are kinda broken here. I tested the sample inputs and everything worked ?? 

mrmajumder:
20191130 07:27:49
4.89 seconds and 79 MB :)


spojmehedi:
20191007 22:32:50
Be carefull about Overflow..10 WA..Finally AC


noble_mushtak:
20190706 18:07:13
This is actually a rather straightforward problem, in my opinion. Solved in two tries (first try, I forgot to put a small line of code). 9.32 seconds and 248 MB in C++14. However, factoring in O(sqrt(n)) is not necessarily fast enough. I was able to handle each query in O(π(sqrt(n))=O(sqrt(n)/log(n)). Last edit: 20190706 18:45:23 
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 