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

1. 1.

   def digit_sum(n):
       s = 0
       while n > 0:
           s += n % 10; n //= 10
       return s
   found = 0
   n = 101
   while found < 5:
       if digit_sum(n) % 7 == 0:
           print(n); found += 1
       n += 1

Ответ: Программа печатает первые пять подходящих чисел

1. 1.

   import math

   def divisors(n):
       res = set()
       for d in range(1, math.isqrt(n) + 1):
           if n % d == 0:
               res.add(d)
               res.add(n // d)
       return sorted(res)

   found = 0
   n = 300001
   while found < 5:
       ds = divisors(n)
       if len(ds) == 4:
           print(n, ds[-2])
           found += 1
       n += 1

2. 2. Функция divisors возвращает отсортированный список всех делителей. Сортировка здесь не роскошь: именно она позволяет взять нужный элемент по индексу.
3. 3. Условие «ровно четыре делителя» проверяется прямо: len(ds) == 4. Кстати, ровно четыре делителя имеют числа вида p·q (произведение двух разных простых) и p³.
4. 4. Наибольший делитель, отличный от самого числа, — это предпоследний элемент отсортированного списка, то есть ds[-2]. Последний элемент ds[-1] — само число.
5. 5. Счётчик found и слово while обеспечивают ровно пять строк вывода: как только найдено пятое число, цикл прекращается.
6. 6. Порядок вывода — число, пробел, сопутствующая величина — задан условием, и менять его нельзя.
7. 7. Оценка времени. Для каждого n делается около √n ≈ 550 операций; пяти подходящих чисел программа достигает быстро, так что запас по времени большой.

Ответ: Программа печатает пять строк вида «число делитель»

1. 1.

   import math

   def deliteli(n):
       res = set()
       for d in range(1, math.isqrt(n) + 1):
           if n % d == 0:
               res.add(d)
               res.add(n // d)
       return sorted(res)

   naydeno = 0
   n = 600000
   while naydeno < 5:
       n += 1
       ds = deliteli(n)
       if len(ds) == 6:
           print(n, ds[-2])
           naydeno += 1

2. 2. Шаг 1. Результат: 600004 и 300002; 600025 и 120005; 600044 и 300022; 600143 и 12769; 600147 и 200049.
3. 3. Шаг 2. Проверим первую находку. 600 004 = 2² · 150 001, где 150 001 простое. Делители: 1, 2, 4, 150 001, 300 002, 600 004 — ровно шесть ✔ Наибольший собственный 300 002.
4. 4. Шаг 3. Теория, объясняющая, какие числа сюда попадают. Если n = p^a · q^b · …, то число делителей равно (a+1)(b+1)…. Шестёрка раскладывается как 6 = 6 или 6 = 2 · 3, значит подходят числа вида p⁵ и p²·q (p и q — разные простые).
5. 5. Шаг 4. Сверим с находками: 600 004 = 2² · 150 001 — это p²·q ✔ 600 025 = 5² · 24 001 — тоже ✔ 600 143 = 47² · 271? Проверим по делителям: 1, 47, 113, 5311, 12769, 600143. Здесь 12 769 = 113², значит 600 143 = 47 · 113², и это снова вид p²·q, только квадрат у другого множителя.
6. 6. Шаг 5. Чисел вида p⁵ среди находок нет, и это ожидаемо: пятые степени простых встречаются крайне редко (ближайшие к 600 000 — это 7⁵ = 16 807 и 11⁵ = 161 051, оба сильно меньше).
7. 7. Шаг 6. Зачем знать теорию, если есть программа. Она даёт проверку правдоподобия: если бы программа нашла число вида p·q (четыре делителя) или p·q·r (восемь), значит ошибка в подсчёте. И она же подсказывает, как ответить на вопрос «сколько делителей у числа 2³·3²·5» без перебора: (3+1)(2+1)(1+1) = 24.
8. 8. Шаг 7. Про math.isqrt вместо int(n ** 0.5). Первая функция считает целочисленный корень точно, вторая идёт через дробную арифметику и на больших числах может ошибиться на единицу — тогда последний делитель потеряется. В задачах линии 25 берите isqrt.

Ответ: 600004 300002; 600025 120005; 600044 300022; 600143 12769; 600147 200049

1. 1.

   def mnozhiteli(n):
       m = []
       d = 2
       while d * d <= n:
           while n % d == 0:
               m.append(d)
               n //= d
           d += 1
       if n > 1:
           m.append(n)
       return m

   print(mnozhiteli(5880))

2. 2. Шаг 1. d = 2. Внутренний цикл делит, пока делится: 5880 : 2 = 2940, 2940 : 2 = 1470, 1470 : 2 = 735. Записано три двойки, n стало 735. Дальше 735 на 2 не делится — внутренний цикл выходит.
3. 3. Шаг 2. d = 3. 735 : 3 = 245 — записана тройка, n стало 245. На 3 больше не делится.
4. 4. Шаг 3. d = 4. 245 на 4 не делится. Обратите внимание: составные делители проверяются впустую, но это безвредно — все их простые множители уже вынесены раньше, поэтому четвёрка в разложение попасть не может.
5. 5. Шаг 4. d = 5. 245 : 5 = 49 — записана пятёрка, n стало 49.
6. 6. Шаг 5. d = 6: не делится. d = 7: 49 : 7 = 7, записана семёрка, n стало 7; 7 : 7 = 1, записана вторая семёрка, n стало 1.
7. 7. Шаг 6. Теперь d = 8, и условие 8 * 8 <= 1 ложно — внешний цикл заканчивается. Остаток n равен единице, значит строка if n > 1 ничего не добавляет.
8. 8. Шаг 7. Результат: [2, 2, 2, 3, 5, 7, 7], то есть 5880 = 2³ · 3 · 5 · 7². Проверка: 8 · 3 · 5 · 49 = 8 · 735 = 5880 ✔
9. 9. Шаг 8. Зачем нужна строка if n > 1: m.append(n). Она дописывает последний простой множитель, который больше корня. Пример: для 26 цикл дойдёт до d = 5 (5·5 = 25 ≤ 26), тринадцать не найдёт, и без этой строки разложение вышло бы [2] вместо [2, 13]. В линии 25 именно числа с крупным простым множителем обычно и требуются — забыть строку значит потерять все находки.
10. 10. Шаг 9. Что из разложения получается дальше. Количество делителей — произведение (степень + 1) по всем простым. Сумма делителей, наибольший собственный делитель (это n, делённое на наименьший множитель), полупростота (ровно два множителя с учётом кратности) — все свойства линии 25 читаются прямо из списка.

Ответ: [2, 2, 2, 3, 5, 7, 7], то есть 2³ · 3 · 5 · 7²

1. 1.

   import math

   def summa_sobstvennyh(n):
       s = 1                       # единица — делитель любого n > 1
       for d in range(2, math.isqrt(n) + 1):
           if n % d == 0:
               s += d
               if d != n // d:     # для полного квадрата не считаем корень дважды
                   s += n // d
       return s

   for n in range(2, 10001):
       if summa_sobstvennyh(n) == n:
           print(n)

2. 2. Шаг 1. Почему s стартует с единицы, а цикл — с двойки. Единица делит любое число и всегда входит в сумму собственных делителей, а само n — не входит по условию. Начав цикл с двойки и не добавляя n, мы получаем ровно нужную сумму.
3. 3. Шаг 2. Зачем проверка d != n // d. Для полного квадрата, скажем n = 36 и d = 6, оба числа пары совпадают, и без проверки шестёрка добавилась бы дважды. Это классическая ошибка подсчёта делителей.
4. 4. Шаг 3. Трассировка для n = 28. s = 1. d = 2: 28 % 2 = 0 → s += 2 (s = 3), парный 14 ≠ 2 → s += 14 (s = 17). d = 3: не делится. d = 4: делится → s += 4 (s = 21), парный 7 ≠ 4 → s += 7 (s = 28). d = 5: 5 * 5 = 25 <= 28, не делится. Цикл кончается, так как math.isqrt(28) равен 5.
5. 5. Шаг 4. Итог: сумма собственных делителей 28 равна 28 — число совершенное ✔ Проверим руками: делители 1, 2, 4, 7, 14, и 1 + 2 + 4 + 7 + 14 = 28 ✔
6. 6. Шаг 5. Программа печатает 6, 28, 496, 8128 — все совершенные числа до десяти тысяч. Их поразительно мало: следующее после 8128 равно 33 550 336.
7. 7. Шаг 6. Сколько это стоит по времени. Внешний цикл проходит 10 000 чисел, внутренний — до корня, то есть не больше 100 витков. Итого около миллиона операций, доли секунды. Наивная версия с перебором делителей до самого n дала бы 50 миллионов — уже секунды.
8. 8. Шаг 7. Та же заготовка отвечает и на соседние вопросы линии 25: «сумма делителей больше самого числа» (избыточные числа), «сумма делителей меньше» (недостаточные), «сумма делителей равна заданному значению». Меняется только сравнение в последней строке.

Ответ: 6, 28, 496, 8128