4-я олимпиада им. Шалтая Смагулова, 6 класс, 1 тур

Дано число $A=\underbrace{13 \cdot 13 \cdot \ldots \cdot 13}_{100 \text{ раз}}$ (т.е. когда число 13 умножили на самого себя 100 раз, получили число $A$). Из числа $A$ вычли наибольший его делитель, не равный самому числу. Из полученной разности также вычли наибольший её делитель, не равный ей самой, и т.д. После пяти вычитаний получили число $B$. Какое частное получится, если $A$ разделить на $B$?

Комментарий/решение

Для начала найдём число а. Для этого возводим 13 в степень 100:

a = 13^100

Теперь нужно найти наибольший делитель числа а, не равный самому числу. Для этого можно перебирать делители от наибольшего к наименьшему до тех пор, пока не найдётся такой делитель.

Найдём наибольший делитель числа а, не равный самому числу:

a_del = 13^99

Теперь вычтем из числа а его наибольший делитель:

b = a - a_del = 13^100 - 13^99

Найдём наибольший делитель числа b, не равный самому числу:

b_del = 13^98

Вычтем из числа b его наибольший делитель:

c = b - b_del = 13^100 - 2*13^99 + 13^98

Продолжим этот процесс ещё три раза:

d = c - 13^97 = 13^100 - 3*13^99 + 3*13^98 - 13^97

e = d - 13^96 = 13^100 - 4*13^99 + 6*13^98 - 4*13^97 + 13^96

f = e - 13^95 = 13^100 - 5*13^99 + 10*13^98 - 10*13^97 + 5*13^96 - 13^95

Теперь можно найти частное а/Б:

a/B = 13^100 / f

Подставив значение f, получим ответ:

a/B = 13^100 / (13^100 - 5*13^99 + 10*13^98 - 10*13^97 + 5*13^96 - 13^95)