VIKRAM91's blog

What is trick behind spoj problem-ABA12D — Sum of divisors!
By VIKRAM91, 6 years ago, In English

can anyone tell me what is trick behind this problem?

  • Vote: I like it
  • -10
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

No

→ Reply
»
6 years ago, # |
  Vote: I like it +14 Vote: I do not like it

I wouldn't call it trick though. Sum of divisors of number n = p1α1p2α2...pkαk is S = (1 + p1 + p12...p1α1)(1 + p2 + p22...p2α2)...(1 + pk + pk2...pkαk). If you want proof, consider small k's for getting logic or even you can induct on k. If k > 1, there are more than one  > 1 multiplications in S, so it wouldn't be prime number. Only case you need to check is k = 1 so only the numbers pα can be "K-number" where p is prime and α is non-negative integer. I think it is enough to solve the problem.

→ Reply