Мы уже разобрали четыре типа задания 15. Остался ещё один, встречающийся в сборниках: задачи с множеством всех натуральных делителей. Сначала поймём их математический смысл, а затем соберём программное решение.
Задания данного типа характерны наличием фразы «множество всех натуральных делителей». В остальном же здесь присутствуют привычные нам отрезки и логическое выражение. Вот только найти здесь надо не какое-то значение числа из выражения, не длину отрезка, а число, делители которого составляют некоторое непустое множество C, фигурирующее в логическом выражении.
Несмотря на необычную формулировку, перед нами снова задача о включении множеств. Только теперь точки множества C расположены не сплошным отрезком, а являются отдельными делителями числа y.
Поэтому сначала разберём математический смысл условия без программы, а уже затем научим Python строить нужное множество полностью и без пропусков.
Нам понадобятся обычные логические операторы, функция all и аккуратный поиск всех собственных делителей числа, то есть делителей без 1 и самого числа.
Собственным делителем здесь будем называть натуральный делитель, отличный от 1 и самого числа. Например, у 12 это числа 2, 3, 4 и 6.
У простого числа таких делителей нет. Поэтому условие отдельно говорит, что C непусто: простые значения y рассматривать нельзя.
Давайте же приступим к разбору алгоритма решения пятого типа 15 заданий!
Формула (x ∈ C) → ((x ∈ A) ∧ ¬(x ∈ B)) должна быть истинна при любом x. Если x не входит в C, импликация истинна автоматически.
Значит, проверять нужно только элементы C. Каждый собственный делитель y обязан одновременно лежать в отрезке A и не принадлежать множеству B.
На языке множеств получаем короткую запись: C ⊆ A \ B. Читается она так: C является подмножеством разности A и B.
Именно эта фраза должна оставаться в голове во время решения: «все собственные делители y разрешены отрезком A и не запрещены множеством B».
Сразу отметим, что заданий данного типа немного, в данной статье будут представлены два примера из сборника Крылова и одно авторское задание. Начнём с такой формулировки из сборника:
На числовой прямой дан отрезок A = [3; 60]; B – множество всех натуральных делителей числа 177, отличных от единицы и от самого числа 177; C – множество всех натуральных делителей некоторого натурального числа y, отличных от единицы и от самого числа y (число y таково, что множество C непустое).
Укажите наибольшее возможное значение числа y, для которого выражение (x ∈ C) → ((x ∈ A) ∧ ¬ (x ∈ B)) истинно (т.е. принимает значение 1) при любом значении переменной x.
Импликация требует, чтобы каждый x из C одновременно принадлежал отрезку A и не входил в B. Поэтому удобнее сначала найти все собственные делители y, а затем проверить только их.
Разложим фиксированное число: 177 = 3 × 59. Поэтому B = {3, 59}. В отрезке [3; 60] разрешены все числа, кроме этих двух точек.
Итак, у искомого y каждый собственный делитель должен лежать от 3 до 60 и не равняться 3 или 59. Уже сейчас задача стала гораздо конкретнее.
Как найти все делители и ничего не потерять?
Делители возникают парами. Если d делит n, то вместе с ним делителем будет n / d. Например, для 36 пары выглядят так: 2 и 18, 3 и 12, 4 и 9, 6 и 6.
Достаточно перебирать d только до квадратного корня. После корня пары начнут повторяться в обратном порядке: проверка 12 снова приведёт к уже найденной паре 3 и 12.
Функция isqrt возвращает целую часть квадратного корня без погрешности вещественных чисел. Множество set автоматически убирает повтор у чисел-полных квадратов (это те, которые являются квадратом целого числа, как 36 здесь).
Давайте сначала напишем код функции, а затем его подробно разберём:
from math import isqrt
def proper_divisors(n):
divs = set()
for d in range(2, isqrt(n) + 1):
if n % d == 0:
divs.add(d)
divs.add(n // d)
divs.discard(n)
return divsПроследим работу функции на числе 84. Целый корень из 84 равен 9, поэтому d пробегает значения от 2 до 9.
При d = 2 остаток равен нулю, и мы добавляем пару 2 и 42. При d = 3 — пару 3 и 28, при d = 4 — пару 4 и 21.
Числа 5 и 6 проверяются дальше: 5 не делит 84, а 6 делит и добавляет 6 и 14. При d = 7 появляется пара 7 и 12. Значения 8 и 9 не подходят.
В итоге функция вернёт {2, 3, 4, 6, 7, 12, 14, 21, 28, 42}. Делители 1 и 84 отсутствуют, как и требует условие.
Строка divs.discard(n) служит дополнительной страховкой. При текущем переборе от 2 само n в множество не попадёт, но явное удаление подчёркивает правило: само число собственным делителем не считается.
Почему перебор конечный? Если y составное, то у него есть пара собственных делителей d и y // d. Оба должны лежать в A, поэтому не превышают 60. Значит, y ≤ 60² = 3600.
Поясним оценку подробнее. У любого составного y есть делитель d не больше √y (записью «√Y» мы будем обозначать квадратный корень числа Y) и парный делитель y / d не меньше √y. Оба они собственные и должны попасть в C.
Если все элементы C не превышают правую границу 60, то и больший делитель пары не превышает 60. Следовательно, √y ≤ 60 и y ≤ 3600.
Эта граница включает все возможные ответы. Она не гарантирует, что каждое число до 3600 подходит, но гарантирует, что выше ответа уже быть не может.
Для каждого y получаем полное множество его собственных делителей:
from math import isqrt
def proper_divisors(n):
divs = set()
for d in range(2, isqrt(n) + 1):
if n % d == 0:
divs.add(d)
divs.add(n // d)
divs.discard(n)
return divs
for y in range(60 ** 2, 1, -1):
divs = proper_divisors(y)Посмотрим, что произойдёт с квадратом простого числа. Для y = 53² = 2809 функция найдёт d = 53 и добавит 53 и 2809 / 53, то есть снова 53. В множестве останется одна точка {53}.
Число 53 лежит в [3; 60], не делит 177 и потому не входит в B. Значит, y = 2809 действительно подходит.
Множество C должно быть непустым. Каждый его элемент x должен лежать в [3; 60] и не быть собственным делителем 177:
from math import isqrt
def proper_divisors(n):
divs = set()
for d in range(2, isqrt(n) + 1):
if n % d == 0:
divs.add(d)
divs.add(n // d)
divs.discard(n)
return divs
for y in range(60 ** 2, 1, -1):
divs = proper_divisors(y)
if divs and all(3 <= x <= 60 and 177 % x != 0 for x in divs):Разберём условие all по частям. Для каждого x из divs сначала проверяется 3 ≤ x ≤ 60, а затем — что 177 % x != 0.
Если хотя бы один делитель вышел из отрезка [3; 60] или оказался делителем фиксированного числа 177, результат all сразу станет False. Остальные элементы можно уже не проверять: кандидат y всё равно отброшен.
Если множество divs пусто, all формально вернул бы True. Именно поэтому перед ним стоит отдельная проверка divs: она исключает простые y и выполняет требование о непустом C.
Всё, как только условие станет истинным, то выводим текущее значение y и завершаем работу программы:
from math import isqrt
def proper_divisors(n):
divs = set()
for d in range(2, isqrt(n) + 1):
if n % d == 0:
divs.add(d)
divs.add(n // d)
divs.discard(n)
return divs
for y in range(60 ** 2, 1, -1):
divs = proper_divisors(y)
if divs and all(3 <= x <= 60 and 177 % x != 0 for x in divs):
print(y)
breakДавайте проверим работу нашей программы. Запускаем её и видим на экране число 2809. А это и есть ответ на данное задание!
Почему программа не выбирает, например, 59² = 3481? Его единственный собственный делитель 59 входит в запрещённое множество B, поэтому условие all ложно.
А 60² тоже не подходит: у него много собственных делителей, среди которых есть числа меньше 3 и числа, запрещённые делимостью 177. Перебор последовательно отбрасывает такие кандидаты.
Мы идём сверху вниз, поэтому 2809 — не просто подходящее значение, а первое подходящее и, следовательно, наибольшее.
Общая заготовка для A = [left; right] и множества B из делителей fixed_number (фиксированного числа. Здесь это было 177):
from math import isqrt
def proper_divisors(n):
divs = set()
for d in range(2, isqrt(n) + 1):
if n % d == 0:
divs.add(d)
divs.add(n // d)
divs.discard(n)
return divs
for y in range(right ** 2, 1, -1):
divs = proper_divisors(y)
if divs and all(
left <= x <= right and fixed_number % x != 0 for x in divs):
print(y)
breakДавайте по этому же алгоритму решим еще одно задание из сборника:
На числовой прямой дан отрезок A = [7; 26]; B – множество всех натуральных делителей числа 77, отличных от единицы и от самого числа 77; C – множество всех натуральных делителей некоторого натурального числа y, отличных от единицы и от самого числа y (число y таково, что множество C непустое).
Укажите наименьшее возможное значение числа y, для которого выражение (x ∈ C) → ((x ∈ A) ∧ ¬ (x ∈ B)) истинно (т.е. принимает значение 1) при любом значении переменной x.
Здесь ищем наименьшее y, поэтому перебор идёт по возрастанию. Верхняя граница равна 26²:
Снова сначала разбираем множества. Число 77 = 7 · 11, поэтому B = {7, 11}. Разрешены собственные делители из [7; 26], кроме 7 и 11.
Число 169 = 13² имеет единственный собственный делитель 13. Он лежит в отрезке A и не входит в B, поэтому 169 подходит.
Но почему оно наименьшее? На этот вопрос отвечает направление перебора: программа проверяет все y от 2 до 168 раньше него и отбрасывает каждое. Первое найденное значение автоматически минимально.
from math import isqrt
def proper_divisors(n):
divs = set()
for d in range(2, isqrt(n) + 1):
if n % d == 0:
divs.add(d)
divs.add(n // d)
divs.discard(n)
return divs
for y in range(2, 26 ** 2 + 1):
divs = proper_divisors(y)
if divs and all(7 <= x <= 26 and 77 % x != 0 for x in divs):
print(y)
breakЗапускаем нашу программу и видим результат — число 169. Его и запишем в ответ.
И напоследок рассмотрим задание с авторской формулировкой:
На числовой прямой дан отрезок A = [2; 47]; B – множество всех натуральных делителей числа 69, отличных от единицы и от самого числа 69; C – множество всех натуральных делителей некоторого натурального числа y, отличных от единицы и от самого числа y (число y таково, что множество C непустое).
Укажите такое значение числа y, имеющее максимальное количество делителей, для которого выражение (x ∈ C) → ((x ∈ A) ∧ ¬ (x ∈ B)) истинно (т.е. принимает значение 1) при любом значении переменной x.
Обратите внимание, что теперь есть дополнительное условие для y. Мы ищем не просто наибольшее или наименьшее значение этого числа, а то, которое имеет максимальное количество делителей! Давайте посмотрим, как это повлияет на наш код.
Здесь нельзя остановиться на первом подходящем y. Нам нужно сравнить все подходящие числа по другой характеристике — количеству делителей.
Код считает собственные делители. Если считать все натуральные делители, к каждому набору добавились бы 1 и само y. Это одинаковые два элемента для каждого кандидата, поэтому победитель не изменится.
Функция proper_divisors остаётся той же. Меняются только отрезок A, число 69 и способ выбора ответа.
from math import isqrt
def proper_divisors(n):
divs = set()
for d in range(2, isqrt(n) + 1):
if n % d == 0:
divs.add(d)
divs.add(n // d)
divs.discard(n)
return divsВ res будем сохранять пары: количество собственных делителей и само y.
res = []Перебираем все y до 47² и проверяем их полные множества делителей:
for y in range(2, 47 ** 2 + 1):
divs = proper_divisors(y)
if divs and all(2 <= x <= 47 and 69 % x != 0 for x in divs):Для каждого подходящего y сохраняем len(divs) и само число:
res.append((len(divs), y))Функция max сначала сравнит первые элементы кортежей — количества делителей. Затем по индексу 1 получим y:
Например, пары (4, 72) и (6, 80) сравниваются сначала по первому числу. Шесть больше четырёх, поэтому выигрывает y = 80.
Если количества совпадут, обычный max выберет пару с большим y. Если условию задачи нужен меньший y при равенстве, правило сравнения следует записать отдельно.
from math import isqrt
def proper_divisors(n):
divs = set()
for d in range(2, isqrt(n) + 1):
if n % d == 0:
divs.add(d)
divs.add(n // d)
divs.discard(n)
return divs
res = []
for y in range(2, 47 ** 2 + 1):
divs = proper_divisors(y)
if divs and all(2 <= x <= 47 and 69 % x != 0 for x in divs):
res.append((len(divs), y))
print(max(res)[1])После запуска программы мы увидим на экране число 80. Оно и будет ответом на это задание.
В пятом типе задания 15 мы прочитали импликацию как включение множеств: все собственные делители y должны лежать в разрешённой части отрезка A и не попадать в B. После такого перевода длинная формулировка превращается в понятную проверку каждого элемента C.
Как собрать решение с нуля:
Шаблон решения
from math import isqrt
def proper_divisors(number):
divisors = set()
for d in range(2, isqrt(number) + 1):
if number % d == 0:
divisors |= {d, number // d}
divisors.discard(number)
return divisors
for y in *1:
divisors = proper_divisors(y)
if divisors and all(*2 for x in divisors):
print(y)
breakВ шаблоне *1 заменяется полным range. Например, для максимума при правой границе 60 пишем range(60 ** 2, 1, -1), а для минимума — range(2, 60 ** 2 + 1).
Вместо *2 записываем проверку одного делителя x. Для формулы из наших примеров это left <= x <= right and fixed_number % x != 0.
Не меняйте устройство шаблона без причины: сначала получаем divisors, затем проверяем непустоту, потом применяем all. Такой порядок соответствует математическому рассуждению и легче проверяется глазами.
Здесь *1 — обоснованный диапазон и направление перебора y, *2 — условие для делителя x. Если нужен экстремум (минимум или максимум) по дополнительной характеристике, сохраняйте пары в список и выбирайте min или max.
Всегда обращайте внимание на слово «непустое»: простые y необходимо исключать. Помните, что делители идут парами, поэтому перебор до √y должен добавлять оба числа. Границу y обосновывайте правым концом отрезка, а направление перебора — словом «наибольшее» или «наименьшее».
Если требуется максимум по количеству делителей, не завершайте цикл на первом кандидате. Сохраните все подходящие варианты вместе с их характеристикой и только затем выберите лучший.
На этом мы закончили разбор всех пяти типов задания 15 ЕГЭ по информатике. Теперь осталось превратить алгоритмы в навык — для этого переходите в наш тренажёр и попробуйте сначала объяснять каждую проверку словами, а уже затем писать код.
