И снова задача на длинную арифметику и/или на математику. Сначала внимательно читаем условие:
Важно при прочтении обратить внимание, что надо найти НОД не входных чисел, а чисел, состоящих из n и m единиц.
Если мы пишем решение на Python, то можем воспользоваться всей мощностью языка и сделать ровно то, как описано в задаче:
- считаем два числа
- построим два длинных числа
- вызовем встроенную функцию для нахождения НОД
Здесь мы довольно хитро построили длинные числа - сначала построили строки из единичек нужной длины, а потом преобразовали их к числовому типу данных.
Чтобы лучше понять алгоритм Евклида, напишем решение без использования длинной арифметики. Нам понадобится пара свойств НОД:
- НОД(a, b) = НОД(a - b, b)
- НОД(a * b, c) = НОД(a, c) * НОД(b, c)
Давайте посмотрим, как это будет работать для чисел из единичек. Сначала из большего числа (N = '1' * n) вычтем меньшее (M = '1' * m):
N - M = 11...11100...000 = 11...111 * 100...000
Если теперь применить второе свойство (мультипликативность):
НОД(N, M) =
НОД(N - M, M) =
НОД(11...111 * 100...000, M) =
НОД(11...111, M) * НОД(100...000, M) =
НОД(11...111, M)
Здесь мы сразу воспользовались тем, что наибольший общий делитель чисел 100...000 и 11...111 равен единице (так у первого числа простыми делителями являются только 2 и 5, а второе число на них не делится).
Такой последовательностью рассуждений мы пришли к тому, что НОД двух чисел из единичек равен НОДу двух чисел из единичек, но у большего числа единичек на m меньше. То есть, по сути, получили тот же алгоритм Евклида, но уже к количеству цифр в числах.
А последний шаг, который мы можем сделать - это заменить встроенную функцию на самописный алгоритм Евклида. К тому же, на Python код станет даже короче:
Если в этом решении убрат два лишних символа, то получим самое короткое решение, которые на данный момент есть на сайте. Но мы делать этого не будем, потому что теряется читабельность кода.
Предыдущий выпуск: Задача 36. Постулат Бертрана
Я очень хочу, чтобы мои советы были полезны вам, а для того, чтобы быстрее всех получать новые статьи можно подписаться на мой канал.