X^a = b (mod 2k + 1)

Anyone could give me a hint about how to approach http://www.spoj.pl/problems/NUMG/ ?

I think you should ask one of the 12 ppl ( http://www.spoj.pl/ranks/NUMG/ ) who have solved this :slight_smile: Just kidding, hope someone turns up to give you some hint.

unless i misunderstand the problem statement, it looks like a discrete logarithm problem.

the only unusual thing is that your task is not to find an answer, but the number of answers.

the first thing i would try (i dunno if it’s correct or not, just intuition), is to find every cyclic solution.

i mean, solutions of the form Xi = ( Y + k * i ). the Xi ^ a could be expanded with the binomial theorem.

if every Xi is a solution, and no other number is, then the number of solutions is easy to guess within the given range.

did you try that ? i’ll have a look if i can find some time. :slight_smile:

In discrete logarithm you have to find the exponent, but here you have to find the base.

you’re right :slight_smile: it “looks like”, but isn’t. did you try what i mentionned ?