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 22warning: a naive algorithm may not run in time.
I got 4.90 sec!
Bin Jin please check my submission as it takes <2seconds on ideone.com but here it shows tle
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?
DoneLast edit: 2016-09-29 13:54:35
@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.
I got AC in 11s :( .... Can somebody give idea about optimization??
Finally AC!!! A very Challenging Problem! Look out for overflows & it is sum of "proper" divisors.
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.