SPOJ.com - Problem DIVSUM2

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.

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.

One integer each line: the divisor summation of the integer given respectively.

Input:
3
2
10
20

Output:
1
8
22

warning: a naive algorithm may not run in time.

< Previous 1 2 3 Next >

	oualiamine: 2017-03-20 22:12:50 what does 1e16 means? =(Francky)=> 1×10¹⁶ Last edit: 2017-03-21 08:12:14
	kira28: 2017-01-04 21:13:04 Finally !!!! xD
	square1001: 2016-07-26 06:21:28 I got 4.90 sec! The time complexity is O(n^0.5 log n + qπ(n^0.5)).
	nightwolf_9197: 2016-02-19 13:15:56 Bin Jin please check my submission as it takes <2seconds on ideone.com but here it shows tle
	ashish kumar: 2015-12-26 15:24:25 I am using optimized sieve with miller rabin test to check for prime and a sqrt time divisor function after all my time is about 4.5 secs. But @Lakshman and some other they got exceptionally less time . How it is possible?
	Bhuvnesh Jain: 2015-07-22 06:00:51 Done Last edit: 2016-09-29 13:54:35
	[Lakshman]: 2015-07-13 18:10:50 @Mohib if you are using seive with trial division you can do it in less than 4s with optimized seive and divisor function. If you want more faster algorithm go for Pollard Rho.
	:.Mohib.:: 2015-07-13 16:53:24 I got AC in 11s :( .... Can somebody give idea about optimization??
	Ouditchya Sinha: 2013-06-23 20:58:07 Finally AC!!! A very Challenging Problem! Look out for overflows & it is sum of "proper" divisors.
	Nic Roets: 2011-07-17 03:56:49 Just to make it clear: The 500 test numbers were not randomly chosen. They were chosen to make the run time as long as possible.