Hello everyone, I was trying to solve this problem but i couldnt handle it, could someone please help me? Given n 1 <= n <= 10^9 we have to find if there is a number which sum of divisors (including that number as a divisor) is equal to n and print it otherwise we have to print -1.
For example Input : 7; Output : 4, Since 7 = 4 + 2 + 1 Input : 1767 Output : 1225 Since 1767 = 1 + 5 + 7 + 25 + 35 + 49 + 175 + 245 + 1225
I don't get it :/
I think it's related to this problem: http://www.spoj.com/problems/INVDIV/
if x = p1k1p2k2... pmkm
then sum of divisors of x equal to (1 + p1 + p12 + ... + p1k1)(1 + p2 + p22 + ... + p2k2)... (1 + pm + pm2 + ... + pmkm)
But how to do for n = 109 ? trying every number leads to O(n * log(n)) if prime factorisation done in log(n) . cannot find a pattern to use
There is a paper about this.