Задача 10.
Известно, что запись числа A в позиционных системах счисления с основанием p и q имеет вид бесконечной периодической дроби с периодом 2:
A = O,(ab) = O,(ba) (*)
где a и b - различные цифры в этих системах счисления.
Написать программу, которая для введенных натуральных чисел p и q (2<=p,q<=30, p>q) находит и выводит все возможные пары значений цифр a и b, удовлетворяющих соотношению (*). Если таковых нет, вывести сообщение 'Пригодных цифр нет'.
Предусмотреть защиту от ввода ошибочных данных.
Примечание: Значением числа, запись которого в позиционной системе счисления с основанием S есть 0, cdef (где c,d,e,f - цифры), являются
|
Решение задачи 10.
Так как q<p, то цифры a и b должны лежать в пределах от 0 до q-1.
Распишем A в системе с основанием p:
A= ... = (ap+b)(p-2) + p-4 + ...) = { находим сумму бесконечно убывающей геометрической прогрессии со знаменателем p-2} =
=
Аналогично для A в системе с основанием q выполняется
A=
Получаем
(bq+a)(p2-1)=(ap+b)(q2-1)
a[p(q2-1)-(p2-1)]=b[q(p2-1)-(q2-1)].
Вычисляем выражения в квадратных скобках; обозначим их соответственно u и v: au=bv.
Находим НОД(u,v)=s; обозначим r=u/s, f=v/s.
Получаем
ar=bf,
r и f взаимно просты, следовательно, решениями этого равенства
будут числа
a=fk, b=rk, k=1,2, ... ,
при этом мы берем только те a и b, для которых одновременно выполняется
а) a<>b
b) a<r
c) b<r
Нахождение НОД - см. задачу 12.
|
