Вход


Главная страница >> Учебный процесс >> Задачник >> Олимпиадные задачи (с решениями) >> Арифметика >> Номер 11

[Назад]    [Содержание ]    [Вперед]

  


Номер 11


  Условие: Номер 11


Задача 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 - цифры), являются

  Решение задачи: Номер 11


Решение задачи 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.

Назад



[Назад]    [Содержание ]    [Вперед]

  


  
За содержание страницы отвечает Гончарова М.Н.
©
Кафедра СПиКБ, 2002-2017