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 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.
In discrete logarithm you have to find the exponent, but here you have to find the base.
you’re right it “looks like”, but isn’t. did you try what i mentionned ?