<ПРЕД Задача:
СЛЕД>
Задачу решили 35 пользователей: 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-адические числа

Time limit = 2 секунд(ы)

Memory limit = 8 Mb

Пусть p — простое число. P-адическим числом (a0, a1, ...)_p будем называть формальную сумму a0 p0 + a1 p1 + ..., где ai — целые числа, 0 ≤ aip-1. Сечением p-адического числа A=(a0, a1, ...)_p длины n будем называть целое неотрицательное число An = a0 p0 + a1 p1 + ... + an pn. Суммой p-адических чисел A и B назовём p-адическое число C = A + B такое, что для любого n выполняется равенство Cn = An + Bn (mod pn+1). Аналогично определяется произведение p-адических чисел.

Единицей назовём p-адическое число E=(1,0,0,0,...)_p. Натуральному числу n поставим в соответствие p-адическое число N, равное сумме E+E+E .. + E из n слагаемых. Например, числу 14 в 3-адической записи будет соответствовать число (2,1,1,0,0,...)_3.

Пусть a и b --- натуральные числа, а A и B --- соответствующие им p-адические числа. Рациональному числу a/b поставим в соответствие p-адическое число X, являющееся решением уравнения B * X = A. В случае, если a и b взаимо просты с p, уравнение имеет единственное решение, причём p-адическая запись (x0, x1, ...)_p числа X периодична. Например, дроби 1/2 соответствует 3-адическое число (2,1,1,1,1,1,...)_3.

Ваша задача — для заданной рациональной дроби построить её p-адическую запись.

Вход В первой строке входного файла записаны три натуральных числа a, b, p, не превосходящие 30000. Числа a, b взаимно просты с p.

Выход В первой строке необходимо записать пару чисел --- длины наименьшего предпериода и периода p-адической записи искомого числа X, а в последующие две строки — цифры предпериода и периода.

Вход#1
1 2 3
Выход#1
1 1
2
1

Вход#2
4 2 7
Выход#2
1 1
2
0

Автор:
Московская студентческая олимпиада 2004.

<ПРЕД | Вернуться к списку задач | Искать сообщения в форуме | СЛЕД>


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

SW soft NIX
ID = 3.209.10.183