checkMate09's blog

How to solve spoj-MMOD29 ?
By checkMate09, history, 8 years ago, In English

hey ,

the problem link : http://www.spoj.com/problems/MMOD29/

i can't figure how to get the divisors of a number that i won't able to store in any data type and i can't think in any path of the problem which i think it's a well-know technique or something like that

any help , thanks :)

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

The main idea to solve this problem is not to store 2004x at all, but to solve it by looking at its prime factorization.

You don't need to get the divisors, you can get the sum itself all at once. Do you know how to do it? I mean, if the problem was to find the sum of divisors of x at some prime mod, could you do it by looking at the prime factors of x?

If you know how to do it, think how you could extend this to 2004x.

If you don't know, wikipedia talks a little about it in an awkward notation, check it here. It is a good read, and the piece you need is the one about σx.

Anyway, that's the main idea you need, but there are some other things that I used.

I reduced the problem to find the sum of a geometric series. This made it necessary to exponentiate and to divide in modulus. Do you know how to do it? Since the prime is small, you could actually brute force division, but it is interesting to understand how that works, and how to do it when the prime is not 29, but 109 + 7.

I hope this helps. Feel free to ask me more things, but take your time to understand the ideas involved in the solution.

→ Reply