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
jenicius: 2023-08-13 16:12:59

The first thing I noticed is that what if n=1 ? It doesn't have any proper divisors so the sum is equal to 0 ?

rouge_kitty: 2022-09-05 17:44:57

Just to make it clear, cpp solutions are getting accepted.

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

Last edit: 2022-09-06 08:32:44
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)).


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