Задание 25 ЕГЭ по информатике: перебор делителей

На отрезке натуральных чисел нужно найти те, что обладают заданным свойством, и вывести несколько первых из них в порядке возрастания. Свойство бывает разным: число делится на заданное, подходит под маску вроде «любая цифра, затем 12, затем что угодно, а в конце пятёрка», у него ровно столько-то делителей. Сложность не в свойстве, а в размере отрезка: перебирать его целиком и для каждого числа честно искать все делители программа не успеет за разумное время, и всё задание сводится к тому, чтобы в нужных местах сделать работу в тысячи раз меньше.

Номер и тему сверяйте по демоверсии 2027 года на сайте ФИПИ. Здесь описаны типы условий, которые держались в последних демоверсиях, без пересказа конкретного варианта. Место задания в работе и общий порядок видны по статье структура ЕГЭ по информатике, а соседнее задание с файлом — это задание 22 про процессы и ресурсы.

Сколько стоит полный перебор

Для иллюстрации возьмём отрезок длиной в миллиард чисел. Чтобы проверить на делители одно число порядка миллиарда, достаточно перебрать кандидатов до его квадратного корня, а это около тридцати тысяч делений. Умножьте на миллиард чисел, и получится порядка тридцати триллионов операций. Python делает десятки миллионов простейших операций в секунду (оценка для обычного компьютера), так что ждать пришлось бы порядка десяти суток; на C++ быстрее на порядок-два, но этого мало. Вывод для любой версии задания один: хотя бы одну из двух частей работы (число кандидатов или цену проверки каждого) нужно сократить кардинально, а лучше обе.

Сокращение цены проверки даёт корень. Если у числа n есть делитель d, то есть и парный n делить на d, и один из двух не превосходит корня из n. Значит, достаточно перебрать d до корня и каждый найденный делитель записывать вместе с парным. Для числа порядка миллиарда это около тридцати тысяч шагов вместо миллиарда. В программе условие остановки цикла записывается как d умножить на d не больше n. Вызов функции корня здесь хуже: вещественный корень на больших числах может дать неточное значение, а умножение целых его не даёт.

Квадрат считается один раз

Тут возникает ловушка, которая стоит баллов чаще остальных. Если n равно d в квадрате, то d и парный делитель совпадают, и считать их дважды нельзя. Возьмите 49. Делители: 1, 7, 49. Собственных, то есть не равных единице и самому числу, один — семёрка. Программа, которая на каждом d добавляет в счёт и d, и 49 делить на d, получит два и решит, что у 49 два собственных делителя. Лечится проверкой равенства: если парный совпадает с самим делителем, добавляется один.

Родственная ловушка спрятана в самом вопросе. «Делители» могут означать все натуральные делители, а могут — только собственные, без единицы и самого числа, и разница ровно в два. Читайте формулировку буквально. Отдельно проверьте простое число: собственных делителей у него нет вовсе, и корректная программа должна вернуть ноль.

Разбор условия про число делителей

Условие придуманное, не из варианта: на отрезке нужно найти числа, у которых ровно два собственных делителя, и для первых пяти вывести сумму этих делителей. Алгоритм записывается словами так. Для каждого кандидата заводятся пустой набор делителей и счётчик. Пробный делитель d идёт от двух, пока d умножить на d не превышает кандидата. Если кандидат делится на d, в набор попадает d, а вместе с ним парный кандидат делить на d, если он отличается от d. Как только в наборе стало больше двух делителей, цикл по d обрывается, потому что кандидат уже не подходит и дочитывать его бессмысленно. По завершении цикла проверяется, что делителей ровно два, и тогда их сумму выводят.

Обрыв по превышению даёт большую часть ускорения: подавляющее число кандидатов имеет много делителей, и они покидают цикл на первых шагах, не доходя до корня. Полный путь до корня проходят только простые числа и те немногие, у кого делителей мало, то есть как раз интересные. Перебор идёт от двойки: так следует из определения собственных делителей; в вашем условии вопрос может быть поставлен иначе, и тогда начало цикла сдвигается.

Полезно знать и устройство ответа: два собственных делителя имеют числа, равные произведению двух разных простых, и кубы простых. Это не нужно для решения, зато нужно для проверки: если среди найденных чисел оказалось одно, которое не раскладывается ни так, ни этак, в программе ошибка. Проверка занимает минуту и ловит сбои, невидимые при чтении кода, например забытое условие про равенство парных делителей.

Дешёвое условие вперёд

Сокращение числа кандидатов основано на том, что свойства имеют разную цену. Проверить, делится ли число на заданное, дёшево: одна операция. Проверить, подходит ли оно под маску, тоже дёшево. Найти делители стоит тысяч операций. Поэтому порядок работы такой: сначала отсекаются числа, не прошедшие дешёвое условие, и дорогую проверку получают только оставшиеся.

Для условия делимости это означает, что кандидатов перебирают с шагом, равным самому числу: стартовое значение — первое кратное, не меньшее начала отрезка, шаг цикла равен самому числу. Если делитель 17, то из каждых семнадцати чисел остаётся одно, и работа сокращается в семнадцать раз без единого условия внутри цикла.

Для маски в Python есть готовое средство: функция fnmatch из одноимённого стандартного модуля, которой передают строковую запись числа и шаблон. Вопросительный знак в ней означает ровно один любой символ, звёздочка — любую цепочку, в том числе пустую, то есть смысл знаков совпадает с условием. Вызов выглядит как **fnmatch(str(n), "?12*5")** и возвращает истину для числа, у которого вторая и третья цифры единица и два, а последняя пять. Ведущего нуля у числа нет, потому что строка получена из целого, и отдельно беспокоиться об этом не надо. Маска сравнивается дёшево, но всё же не бесплатно: если кратность тоже есть в условии, сначала берут кратные (шагом цикла), потом проверяют маску, и только тогда считают делители.

Остановка и вывод

Выводить нужно несколько первых подходящих чисел, и лишнее время программа тратит там, где её не останавливают, когда нужное количество чисел уже найдено. Заведите счётчик найденных и прервите цикл, как только он достиг заданного числа. Для условий с поиском наибольших чисел цикл, напротив, идёт от конца отрезка вниз: первые же найденные числа и есть искомые.

Порядок вывода — по возрастанию, если условие не говорит иное. Рядом с каждым числом выводится требуемая характеристика: частное, наименьший или наибольший делитель, сумма. Ответ в этом задании состоит из нескольких чисел, и опечатка в любом из них портит всё. Что именно стоит в строке, в каком порядке и через какой разделитель, смотрите в демоверсии 2027 года: по публикациям, запись ответа в одном из заданий высокого уровня собираются упростить, и какое именно, надо проверить. Сборка ответа из нескольких чисел вручную — лучше способ ошибиться, поэтому стоит распечатывать числа и копировать вывод, как есть.

Две программы вместо одной

Моя позиция, с которой можно спорить: на этом задании я бы писал сначала глупую программу. Медленную, перебирающую делители до самого n, без отсева и без остановки, зато очевидно верную. Она запускается на отрезке в несколько тысяч чисел и выводит результат. Потом пишется быстрая версия с корнем и остановкой, запускается на том же малом отрезке, и ответы сравниваются. Совпали — быстрая версия честная, и её можно пускать на настоящий отрезок. Не совпали — в быстрой версии ошибка, и найти её проще всего именно на малом отрезке, где можно вывести оба списка и посмотреть на первое расхождение.

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

Куда смотреть, если решение не работает

Различайте причины. Программа верна, но не укладывается во время: нужны корень и отсев, и достаточно проверить, действительно ли вы остановили цикл на корне и взяли кратные. Программа быстрая, но ответ неверный: ищите расхождение на малом отрезке, о чём выше. Идея ясна, но не получается записать цикл с шагом и условием: это пробел в основах языка, и исправляется он на любых задачах с циклами, не обязательно на этом. Делимость и простые числа проходят в основной школе на уроках математики, поэтому сама арифметика знакома, а вот превращение её в цикл — навык информатики, и он плохо тренируется чтением.

Похожую дисциплину (оценить цену перебора заранее и найти место, где можно сэкономить в тысячи раз) вы встретите и в последней задаче работы, которая разобрана в статье про обработку большого файла в задании 27. Про выбор между Python и C++ для заданий, где важна скорость, написано в статье Python или C++ для ЕГЭ. А с неизвестной цифрой и делимостью вы уже встречались в задании 14 про системы счисления. Общую карту первой части даёт разбор первой части ЕГЭ по информатике, а курс в школе — статья информатика в школе: что учить и в каком порядке.

Начать поиск:

• репетиторы по информатике для подготовки к ЕГЭ
• все репетиторы для подготовки к ЕГЭ

Вопросы и ответы

Достаточно ли перебирать делители до корня, если число простое? Да. Если до корня делителей нет, число простое, и дальше искать нечего.

Нужно ли писать на C++, если Python не укладывается во время? Сначала проверьте алгоритм: корень и остановка по числу найденных. В большинстве случаев после этого Python укладывается, а переписывание на другой язык — последний шаг, не первый. Если же отсев сделан, остановка есть и всё равно медленно, тогда C++ оправдан, и вот тогда придётся помнить о переполнении: произведение двух чисел порядка миллиарда уже не помещается в 32 разряда, и промежуточные значения стоит хранить в 64-разрядном типе.

Что делать, если число делителей нужно только у подходящих по маске чисел? Сначала маска, потом делители, как в разделе выше.

Можно ли заранее вычислить все простые числа и не искать делители? Можно, решето Эратосфена помогает, когда отрезок невелик. Для миллиардных значений таблица такого размера уже становится проблемой по памяти, и прямой перебор до корня оказывается проще.

Как вводить ответ, если в нём несколько строк или чисел? Печатайте их программой в том виде, в каком просит условие, и копируйте результат целиком; набирать его заново не нужно. Прежде чем вводить, сверьте число строк с тем, сколько просили, и порядок значений в каждой строке. Если нужно ввести пару через пробел, а у вас в выводе стоит запятая или лишний пробел в конце строки, поправьте это в программе, и при повторном запуске ошибка не вернётся; правка руками в поле ответа этого не даёт. Правила записи многострочного ответа смотрите в инструкции к своему варианту.