|Online MIPT programming contest||РУССКИЙ|
Time limit = 2 second(s)
Memory limit = 8 MbLet p to be a prime number. P-adic number (a0, a1, ...)_p is defined as formal sum a0 p0 + a1 p1 + ..., where ai are integers, 0 ≤ ai ≤ p-1. The section of p-adic number A=(a0, a1, ...)_p of length n is defined as non-negative integer An = a0 p0 + a1 p1 + ... + an pn. The sum of p-adic numbers A and B is another p-adic number C = A + B such for any n, the equality Cn = An + Bn (mod pn+1) holds. Similarly, the product of two p-adic numbers can be defined.
Let's name p-adic number E=(1,0,0,0,...)_p as "one". For each natural number n, let's assign a p-adic number N that is equal to E+E+E .. + E (n items). For example, for natural number 14, in 3-adic notation, we'll assign (2,1,1,0,0,...)_3.
Let a and b to be natural numbers, A and B correspondent p-adic numbers. For rational number a/b, let's assign a p-adic number X, that is the root of equation B * X = A. If a and b are mutually disjoint with p, the equation has the single solution, and p-adic notation (x0, x1, ...)_p of the number X is periodic. For instance, for the fraction 1/2 is associated with 3-adic number (2,1,1,1,1,1,...)_3. Given the fraction, you are to find its p-adic notation.
Input The first line contains three natural numbers a, b, p, that do not exceed 30000. a and b are mutually disjoint with p.
The first line should contain two integers the length of the smallest pre-period and the length of the period of p-adic notation of the required X.
The second and the third line should contain figures of pre-period and period.
1 2 3
1 1 2 1
4 2 7
1 1 2 0
Moscow student's contest, 2004.
© acm.mipt DevGroup
The page was generated in 210ms