:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте ::
Путь: Математика » Теория чисел » Период дроби N/M по основанию P
  Период бесконечной дроби N/M по основанию P



Здесь можно прочитать о решении частного случая задачи:
"Дано натуральное число n>1. Определить длину периода десятичной записи дроби 1/n."

Введем переменную N1=N.

Пусть N1 и M заданы в десятичной системе счисления. Переведем дробь N1/M в систему счисления с основанием p:

Пусть в системе с основанием p искомая дробь 0.a(1)a(2)...

Получаем:

a(1)*p-1+a(2)*p-2+ ... =N1/M.

Умножим правую и левую части равенства на p:

a(1)+a(2)*p-1+ ... = N1*p/M.

Выделяя целую часть выражений слева и справа от знака равенства, получаем

a(1) = целая часть (N1*p/M).

Обозначим N2 = N1*p mod M; очевидным образом получаем

a(2)*p-1+ ... = N2/M.

Домножая на p и находя целую часть, опять же имеем

a(2) = целая часть (N2*p/M);

продолжая аналогично, определяем коэффициенты a(3),a(4) и т.д.

В ходе выделения цифр ai мы можем получить различных значений Ni не более чем M (по алгоритму выше у нас всегда Ni<M).

Если вдруг какие-то два остатка совпадают: Ni=Nj, i<>j, то совпадают и цифры разложения: ai+1=aj+1, ai+2=aj+2, ... , т.е. цифры (ai+1, ... ,aj) образуют один из кратных периодов. Нам надо найти минимальную длину такой периодически повторяющейся последовательности, которая равна количеству цифр между двумя ближайшими повторяющимися остатками, и сами цифры.

Поступаем следующим образом:

Выделяем M цифр p-ичной дроби (исходя из вышесказанного, к этому моменту период уже обязан начаться). Запоминаем Nm, и ищем первый такой остаток Nk, k>m, что Nm=Nk. Величина k-m как раз и есть искомая длина периода.