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
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
maximum_01: 2019-07-02 12:00:46

factorizing in o(root(n)) but still getting tle

frochbg: 2019-05-31 16:16:01

Nice problem with fast factorization :)

scolar_fuad: 2019-04-13 16:00:05

please share idea is any ??

des1997: 2018-06-23 11:50:33

ran in 3.02 seconds:)

karthik1997: 2017-12-28 13:39:05

Can't go below 2s . :(

kmkhan_014: 2017-12-21 16:55:26

this is extremel !!! AC in 15s


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