Hide

Problem P
Hydrationsword Saga

/problems/hi.hydrationswordsaga/file/statement/en/img-0001.png
Image taken from commons.wikimedia.org
The Grand Combat Delusion movie was so bad that quite a few party guests have decided to leave. Thus there aren’t enough people left to stop Atli from selecting the next thing to watch. He puts on his favourite show, Hydrationsword Saga. As time passes Atli begins to talk more and more about the show while it’s going on, leaving little left to be spoiled. He talks at length about the main character’s battle with Angrygon at their side against the dark god and Angrygon’s tragic fate in that battle. He continues babbling, going on and on about the Futon-brothers and their mechs and the AB knight and his fall to the dark side. At this point the group in front of the television is starting to thin quite a bit, but this does not stop Atli. He keeps talking, moving next on to the red scythe, the AB knight’s lackeys and the unforgettable fight when the main character temporarily fell over to the darker side. He then moves on to talk about the battle between the main character and the AB knight and the main character’s eventual victory. But Atli then adds that this is not all, there is yet more to be said. Only the most patient of party guests were still listening, but he told them of the battle against VaurSala and how everyone came together in the end to defeat this might enemy and how much they lost on the way there. Not before long Atli finds himself speaking to an empty room, so he pauses the show. He looks around and sees that everyone has left. He figures he should probably get gong as well then, but on his way home he thinks about the lecture he has to get ready for the competitive programming course. His mind wanders to Floyd’s cycle finding algorithm. ‘What would be a good problem to test people’s understanding of that algorithm?’ he thinks to himself. ‘I have to come up with some interesting function to test it on’ he thinks next. When he finally gets into bed, inspiration strikes. ‘Aha! $f(x) = ax^ b$ will do nicely!’ he thinks before falling asleep. The following day he gets working on the problem. But then he realizes that he has to prepare testing data and a solution to the problem. Since he is too lazy to program he will need your assistance.

Given three numbers $a, b, m$ the assignment is to run Floyd’s cycle finding algorithm on the function $f(x) = ax^ b (\textrm{mod} \ m)$. Let $f^{[n]}(x)$ denote applying $f$ exactly $n$ times on $x$. Running Floyd’s algorithm thus means we want to find the smallest $\mu $ such that $f^{[\mu ]}(x) = f^{[\lambda + \mu ]}(x)$ for all $x$ and some $\lambda > 0$. For this particular $\mu $ one is also to determine the smallest such $\lambda $. $\mu , \lambda $ should then be printed.

Input

The only line in the input contains three integers $a, b, m$ satisfying $0 \leq a, b \leq 10^{15}$ and $1 \leq m \leq 10^{15}$.

Output

Print $\mu $ and $\lambda $ on a single line with a single space between the numbers.

Sample Input 1 Sample Output 1
2 3 17
0 4
Sample Input 2 Sample Output 2
5 7 35
1 6

Please log in to submit a solution to this problem

Log in