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

 < Previous 1 2 3 Next > indrajitsadh: 2021-04-27 20:38:47 Look at languages ....? All except: CPP CPP not accepted? Last edit: 2021-04-27 20:39:13 rupok_03: 2020-10-19 18:30:10 use div_sum = 1LL & bitset for sieve jagonmoy: 2020-07-13 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 . it's very straight forward problem just you need to use bitwise sieve instead of general sieve to store primes up to 10^8 jainapoorv094: 2020-06-11 18:53:50 is the ans fit in long long nurbijoy: 2020-05-18 20:06:08 check out my code. can't get AC. TLE https://ideone.com/6n2YkP arman____: 2020-03-31 21:54:26 got acc in simple SOD...just range and time limit big.. myner: 2019-12-07 12:59:38 can it be that the test cases are kinda broken here. I tested the sample inputs and everything worked ?? mrmajumder: 2019-11-30 07:27:49 4.89 seconds and 79 MB :) Did optimized sieve to find out primes, and later did prime factorizing, and some calculation. Handled each query in O(π(sqrt(n))=O(sqrt(n)/log(n)). spojmehedi: 2019-10-07 22:32:50 Be carefull about Overflow..10 WA..Finally AC noble_mushtak: 2019-07-06 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: 2019-07-06 18:45:23