Тип 2
В предыдущей статье мы познакомились с модулем fnmatch и научились решать задания первого типа, где требовалось находить числа, соответствующие заданной маске. Это был достаточно простой тип задач, решаемый буквально в несколько строк кода благодаря встроенным функциям Python.
Теперь пришло время перейти ко второму типу заданий, который уже немного сложнее первого. Здесь нам предстоит работать с делителями чисел: находить их, подсчитывать количество, проверять различные свойства. Для успешного решения таких задач нужно не только понимать, что такое делитель, но и уметь эффективно находить все делители числа.
Вторым аспектом данного типа является определение последней цифры или нескольких цифр числа. Здесь также есть несколько алгоритмов, разных по эффективности и скорости работы.
Данная статья как раз и посвящена разбору двух этих алгоритмов и решению второго типа 25 заданий ЕГЭ.
Поиск делителей
Давайте начнём с самых основ. Делителем числа называется такое целое число, на которое исходное число делится без остатка. Например, число 6 делится на 1, 2, 3 и 6 — это и есть все его делители.
Чтобы разобраться в алгоритме поиска делителей, возьмём конкретный пример — число 16. Будем искать все его делители и попутно выявлять закономерности, которые помогут нам написать эффективный код.
Начнём с того, что любое целое число всегда делится на само себя и на единицу. Это два делителя, которые есть абсолютно у каждого числа. Значит, для числа 16 мы уже нашли делители 1 и 16.
Теперь проверим промежуточные числа — от 2 до 15. Можно просто мысленно задавать себе вопрос: «Делится ли 16 на это число без остатка?»
Проверяем число 2: да, 16 делится на 2, получается 8. Отлично, нашли ещё один делитель.
Проверяем число 3: нет, 16 на 3 без остатка не делится. Пропускаем.
Проверяем число 4: да, 16 делится на 4, получается 4. Интересно — при делении получилось то же самое число! Это произошло потому, что 16 является полным квадратом, то есть числом, которое можно получить возведением целого числа в квадрат (4 × 4 = 16).
Давайте остановимся и посмотрим на то, что мы уже нашли. Когда мы делили 16 на 2, получили 8. Это значит, что 8 тоже является делителем числа 16! Ведь если 16 : 2 = 8, то верно и обратное: 16 : 8 = 2.
Получается, делители идут парами. Когда мы находим один делитель, мы автоматически находим и второй — нужно просто разделить исходное число на найденный делитель.
В результате мы получили пять делителей числа 16: 1, 2, 4, 8 и 16. Давайте разделим их на группы, чтобы лучше понять структуру:
Первая группа — это единица и само число. Они есть всегда у любого числа.
Вторая группа — квадратный корень числа, но только в том случае, если число является полным квадратом. Для числа 16 это число 4.
Третья группа — парные делители. В нашем случае это пара 2 и 8. Обратите внимание: 2 × 8 = 16, то есть произведение парных делителей всегда равно исходному числу.
А что, если число не является полным квадратом? Для примера рассмотрим число 20. Его делители будут такие: 1, 20; 2, 10; 4 и 5.
При этом корень числа 20 — это чуть больше 4,47. То есть нам достаточно найти все делители до корня из числа. К этому мы еще вернёмся немного позже!
А пока давайте выразим наши рассуждения в коде на Python. Начнём с самого простого и очевидного способа — будем перебирать все числа от 1 до самого числа и проверять, делится ли исходное число на текущее без остатка.
Разберём этот код подробнее. Мы создаём пустой список divisors, в который будем складывать найденные делители. Затем в цикле перебираем все числа от 1 до num включительно. Для каждого числа i проверяем условие num % i == 0 — это проверка на делимость без остатка. Оператор «%» возвращает остаток от деления, и если он равен нулю, значит деление произошло нацело.
Код работает правильно, но есть проблема — он крайне неэффективен. Представьте, что нам нужно найти делители числа 1 000 000. Придётся выполнить миллион итераций цикла! А ведь можно сделать гораздо меньше.
Чтобы не быть голословными, давайте замерим время выполнения кода для поиска делителей числа 1 000 000:
Десять запусков нашей функции get_divisors() заняли почти целую секунду. Да, пока что это кажется небольшим числом. Но далее вы увидите, как сильно можно сократить это время!
Теперь перейдём к оптимизации. Давайте разберёмся на примере. Для числа 16 квадратный корень равен 4. Посмотрим на пары делителей:
- 1 и 16 (произведение равно 16)
- 2 и 8 (произведение равно 16)
- 4 и 4 (произведение равно 16)
Заметьте: в каждой паре один делитель меньше или равен 4 (корню из 16), а другой — больше или равен 4. Это не случайность, а математическая закономерность. Если бы оба делителя в паре были больше корня, их произведение превысило бы исходное число.
Поэтому нам достаточно перебрать числа от 1 до корня из числа. Для каждого найденного делителя мы сразу вычислим его пару делением исходного числа на него.
Давайте наглядно сравним, сколько итераций потребуется для разных способов поиска делителей числа 1 000 000:
- Перебор до самого числа: 1 000 000 итераций.
- Перебор до половины числа: 500 000 итераций. Некоторые думают, что достаточно дойти до половины, ведь делитель не может быть больше половины числа (кроме самого числа). Это верно, но всё равно слишком много.
- Перебор до корня из числа: всего 1 000 итераций! Корень из миллиона равен тысяче.
Разница колоссальная — вместо миллиона операций мы делаем всего тысячу. Это в тысячу раз быстрее!
Осталось лишь научиться извлекать корень из числа в Python. Для этого есть несколько способов. Поскольку нам нужно передать значение в функцию range(), результат должен быть целым числом. Рассмотрим два варианта.
Первый способ — использовать возведение в степень 0,5 и преобразование к целому числу:
Второй способ — использовать специальную функцию isqrt() из модуля math, которая сразу возвращает целочисленный корень:
Какой из них лучше? Давайте проверим на практике. Напишем небольшой тест, который измерит время работы обоих способов:
Функция isqrt() работает примерно в 2 раза быстрее! Поэтому в дальнейшем будем использовать именно её.
Теперь соберём всё вместе и напишем эффективную функцию поиска делителей. Есть ещё один нюанс: вместо списка мы будем использовать множество для хранения делителей.
Почему множество лучше? Во-первых, оно автоматически исключает дубликаты. Это важно для полных квадратов: когда мы находим делитель 4 для числа 16 и вычисляем его пару (16 : 4 = 4), мы получаем то же самое число. В списке оно добавилось бы дважды, а множество сохранит его только один раз.
Во-вторых, проверка наличия элемента во множестве работает быстрее, чем в списке, что может пригодиться в некоторых задачах.
Вот итоговый код:
Разберём ключевые моменты. Мы перебираем числа от 1 до корня из num включительно — для этого добавляем единицу к результату isqrt(). При нахождении делителя i мы добавляем в множество сразу два числа: сам делитель и его пару num // i. Оператор «|=» выполняет объединение множеств, то есть добавляет в divisors оба новых элемента.
А теперь самое интересное — замерим время выполнения и сравним его с прошлой версией этой функции:
Это в тысячу раз быстрее нашей первой функции! Именно такую запись мы и будем использовать при решении 25 заданий.
Поиск последних цифр числа
С поиском делителей мы разобрались. Однако во многих заданиях этого недостаточно — требуется ещё и проанализировать найденные делители. Одна из частых задач — найти среди делителей те, которые оканчиваются на определённую цифру или число. Например, отобрать все делители, последняя цифра которых равна 5, или найти делители, оканчивающиеся на 25.
Давайте разберёмся, как эффективно извлекать последние цифры числа.
Существует два популярных подхода к получению последней цифры числа.
Первый способ — математический. Нужно взять остаток от деления числа на 10. Вспомните, как работает деление с остатком: если разделить 127 на 10, получится 12 и остаток 7. Этот остаток и есть последняя цифра числа.
Второй способ — строковый. Можно превратить число в строку и взять последний символ через индексацию или срез.
Обратите внимание на важное отличие: математический способ возвращает число, а строковый — символ. Это влияет на то, с чем мы будем сравнивать результат.
Что если нужно проверить не одну, а две или три последние цифры? Например, найти числа, оканчивающиеся на 25 или на 100?
Математический способ легко обобщается. Чтобы получить две последние цифры, делим на 100. Чтобы получить три — на 1000. Закономерность простая: делим на 10 в степени, равной количеству нужных цифр.
Строковый способ тоже адаптируется без проблем — просто берём срез нужной длины с конца строки.
Но какому способу отдать предпочтение? В решениях ЕГЭ вы можете использовать любой из этих способов — оба дадут правильный ответ. Но раз уж мы разбираем эффективные алгоритмы, давайте выясним, какой из них работает быстрее.
Проведём эксперимент по аналогии с тем, как мы сравнивали способы извлечения квадратного корня. Создадим две функции: каждая будет перебирать числа от 0 до 1000 и добавлять в множество те, которые оканчиваются на 5.
Математический способ оказался примерно в два раза быстрее строкового!
Результат вполне логичен, если задуматься о том, что происходит внутри каждого способа.
При использовании остатка от деления выполняются всего две операции: вычисление остатка и сравнение двух целых чисел. Обе операции элементарны для процессора.
При строковом подходе всё сложнее. Сначала Python должен преобразовать целое число в строку — это создание нового объекта в памяти, посимвольное формирование представления числа. Затем происходит обращение к последнему элементу строки. И наконец, сравнение двух строк, что тоже чуть медленнее сравнения чисел.
Каждая из этих операций по отдельности занимает доли микросекунды, но, когда цикл выполняется тысячи или миллионы раз, разница накапливается и становится заметной.
Для задач ЕГЭ разница в скорости обычно не критична — программа в любом случае отработает за доли секунды. Однако полезно привыкать к эффективным решениям, поэтому лучше будет использовать математический способ как основной.
Есть и ещё одно преимущество: при математическом подходе вы работаете с числами на протяжении всей программы, не переключаясь между типами данных. Это делает код более единообразным и снижает вероятность ошибок, связанных с путаницей между строками и числами.
Что же, с теорией разобрались, перейдём к решению заданий ЕГЭ.
Алгоритм решения
Первым на очереди у нас будет такое задание:
«Пусть R – сумма всех различных натуральных делителей целого числа.
Напишите программу, которая перебирает целые числа, бо́льшие 500 000, в порядке возрастания и ищет среди них такие, для которых значение R оканчивается на цифру 6.
В ответе запишите в первом столбце таблицы первые пять найденных чисел в порядке возрастания, а во втором столбце – пять соответствующих этим числам значений R.»
Что нам тут нужно сделать:
- Перебрать числа от 500 000
- Найти для каждого делители
- Подсчитать сумму этих делителей
- Если сумма оканчивается на 6, то такое число нам подходит
- Пять таких чисел нужно вывести на экран вместе с суммой их делителей
Здесь логично будет разделить программу на две части: одна функция, которая определяет подходящие под условия числа и цикл, в котором перебираются числа, большие 500 000 и выводятся на экран, если функция возвращает для них истину.
Начнём с функции, импортируем isqrt() и напишем уже разобранный выше код для поиска делителей:
В res у нас хранятся все делители числа num. Теперь подсчитаем число R — сумму делителей. И если остаток от деления R на 10 будет равен 6, то значит, что сумма делителей числа num оканчивается на 6. Следовательно, такое num нам подходит. Но возвращать мы будем не логическое значение, а R — оно и так будет истинным. В противном же случае возвращаем 0 (ложь).
Первая часть готова, перейдём к циклу. Перебирать будем числа от 500 001 до некоторого большого значения, например, до 10 в двадцатой степени. Также заведём отдельную переменную-счётчик cnt, чтобы вывести именно 5 значений:
Далее используем интересный оператор Python, чтобы присвоить переменной res значение функции сразу внутри блока if:
Этот оператор «:=» называется моржовым. Он доступен с версии Python 3.8 и позволяет присваивать значения переменным прямо внутри выражения.
То есть запись «R := f(i):» аналогична вот такой без моржового оператора:
Итак, если функция нам вернёт число (не 0), выведем на экран значение i — текущее перебираемое число в цикле и R — сумму делителей этого числа i:
Не зря же мы добавляли счётчик cnt? После каждого вывода на экран будем увеличивать его значение на 1. И по достижении 5 — прервём цикл оператором break:
На этом всё. Запускаем код и получаем пять пар чисел для ответа:
500032 1070356
500035 606816
500039 501456
500050 949716
500052 1333696
Пример 1
Рассмотрим похожее задание:
«Пусть M – сумма минимального и максимального натуральных делителей целого числа, не считая единицы и самого числа. Если таких делителей у числа нет, то значение M признаётся равным нулю.
Напишите программу, которая перебирает целые числа, бо́льшие 800 000, в порядке возрастания и ищет среди них такие, для которых M оканчивается на 4.
В ответе запишите в первом столбце таблицы первые пять найденных чисел в порядке возрастания, а во втором столбце – соответствующие им значения M.»
Код, показанный выше, довольно оптимально решает поставленную задачу. Но всё же его можно оптимизировать еще больше. Давайте на примере этого задания посмотрим, как повысить скорость работы нашей программы.
Начало будет всё тем же — импорт и начало функции:
Теперь мы не будем создавать множество с делителями. Ведь по условию нам нужны только максимальный и минимальный. И мы помним про принцип «парности» делителей: достаточно найти минимальный делитель, тогда максимальный — это частное от деления самого числа на этот минимальный делитель.
Вот пример: есть число 63. Минимальный его делитель — это 3. Тогда максимальный можем найти так: 63 : 3 = 21. Реализуем это в коде. Сначала проверим, что текущее число i является делителем num:
Если является, то первое же число i будет минимальным делителем, сохраним его в переменную mn:
Делением найдём максимальный:
По условию, M — это сумма минимального и максимального делителей. Так и запишем:
Если это M оканчивается на 4, то возвращаем его. Во всех остальных случаях будет возвращать 0:
Функция готова, а в коде цикла ничего особо менять не будем:
Запустим нашу программу и получим 5 пар чисел:
800004 400004
800009 114294
800013 266674
800024 400014
800033 61554
Их и запишем в ответ на это задание.
Пример 2
В заключение рассмотрим еще одно задание, но уже с отличающейся формулировкой:
«Напишите программу, которая перебирает целые числа, большие 1 350 050, в порядке возрастания и ищет среди них такие, у которых есть натуральный делитель, оканчивающийся на 11 и не равный ни самому числу, ни числу 11.
В ответе запишите в первом столбце таблицы первые пять найденных чисел в порядке возрастания, а во втором столбце — для каждого числа соответствующий минимальный делитель, оканчивающийся на 11, не равный ни самому числу, ни числу 11.»
Первые четыре строки у нас будут всё те же:
Далее нам нужно проверить, что текущий делитель i оканчивается на 11 и при этом не равен 11:
Равенство самому числу num мы не проверяем, само собой.
И таким же образом найдём пару найденному делителю:
Если ничего не подходящего не нашлось — возвращаем 0:
Цикл же каким был, таким и остался:
Запускаем программу и получаем ответ:
1350051 311
1350055 270011
1350062 511
1350063 40911
1350066 225011
Для заданий второго типа мы уже не будем выводить какой-то шаблонный код. Ведь как вы уже заметили, для каждого задания оптимальнее будет искать свой подход. Здесь эффективность решения зависит только от вашей фантазии и навыков программирования:
- Можно вообще избавиться от функций, что немного ускорит программу и позволит использовать меньше локальных переменных.
- Можно менять шаг в цикле перебора делителей. Но главное — делать это осторожно, чтобы случайно не пропустить нужные значения.
- Можно заменить for на while, хотя это не даст особого выигрыша в скорости, так что тут дело вкуса.
Главное — внимательно анализируйте алгоритм и старайтесь найти оптимальное математическое решение. Но помните про баланс — программа может выполняться быстро, но на её написание вы потратите куда больше времени, чем сэкономите. Да и про шанс ошибиться в необычном подходе не стоит забывать!
А в следующей статье мы разберёмся с еще более сложной задачей. Нам предстоит не просто искать делители, но и определять простые числа среди них.