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

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