<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.
UserDateAttemptTimeCMSC
daniel.ugra08 jan 2007Ruby200.20126 
gaoyihan01 dec 2007C++200.04217 
zmy04 jan 2008C++400.05238 
WsemirZ22 mar 2009FPC800.12247 
tourist24 dec 2007Kylix100.13266 
Stranger11 nov 2006FPC600.09273 
WsemirZ22 mar 2009Kylix500.11275 
RAVEman12 mar 2009C++300.06303 
MasterZerg02 jan 2007C++400.10303 
tomek14 apr 2006C++100.03323 
UdH-WiNGeR26 feb 2009Java100.86349 
Languages
C++
27
Kylix
3
FPC
2
Java
1
Ruby
1
Python
1
C
1
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 

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 = 18.207.130.162