<PREV Problem:
NEXT>
Solved by 35 users: DD, tomek, wojtekt, Akd, JohnJones_001, Stranger, MasterZerg, daniel.ugra, mikleb, dan, marek.cygan, EA, andyzh1314, gaoyihan, tourist, zmy, Chmeli_BSU, Zhukov_Dmitry, zloy_mipt, Ravent, mazahaka, pmnox, UdH-WiNGeR, RAVEman, defrager, WsemirZ, Vyshnya, EAA2008, Dest, s01A15, mathematic, NIGHTFIT, Robert_Gerbicz, Fat, avg79.
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

p-adic numbers

Time limit = 2 second(s)

Memory limit = 8 Mb

Let 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 ≤ aip-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.

Output 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.

Input#1
1 2 3
Output#1
1 1
2
1

Input#2
4 2 7
Output#2
1 1
2
0

Author:
Moscow student's contest, 2004.

<PREV | Problem set | Search related messages | NEXT>


© acm.mipt DevGroup
The page was generated in 200ms

SW soft NIX
ID = 54.162.181.75