Типы задач и стратегии решения
ТИП 1: Числа с фиксированным количеством делителей
Формулировка: «Найти числа с ровно K нетривиальными делителями»
Теоретическая основа:
K нетривиальных делителей означает K + 2 делителей всего. По формуле количества делителей нужно найти, какие формы чисел дают именно такое количество.
Поскольку количество делителей — это произведение (a₁ + 1)(a₂ + 1)..., нужно разложить K + 2 на множители:
| Нетривиальных |
Всего делителей |
Разложение |
Форма числа |
| 1 |
3 |
3 = 3 |
p² |
| 2 |
4 |
4 = 4 или 2×2 |
p³ или p×q |
| 3 |
5 |
5 = 5 |
p⁴ |
| 4 |
6 |
6 = 6 или 3×2 |
p⁵ или p²×q |
| 5 |
6 |
6 = 6 или 3×2 |
p⁵ или p²×q |
| 6 |
8 |
8 = 8 или 4×2 или 2×2×2 |
p⁷ или p³×q или p×q×r |
Ключевое наблюдение для 3 нетривиальных делителей:
Число 5 — простое, поэтому его можно представить только как 5 = 5×1. Значит, в разложении числа только один простой множитель в четвёртой степени: n = p⁴.
Делители такого числа: 1, p, p², p³, p⁴ — ровно пять штук, из них три нетривиальных.
Стратегия решения:
Вместо перебора миллионов чисел в заданном диапазоне [A; B] достаточно:
- Найти границы для простого p: от ⁴√A до ⁴√B
- Перебрать только простые числа в этом узком диапазоне
- Для каждого простого p проверить, попадает ли p⁴ в исходный диапазон
Это сокращает перебор с сотен миллионов до нескольких десятков проверок.
ТИП 2: Произведение K различных простых множителей
Формулировка: «Найти числа, являющиеся произведением ровно двух (трёх) различных простых с дополнительным условием»
Теоретическая основа:
Число вида n = p × q (два различных простых) имеет ровно 4 делителя: 1, p, q, pq.
Число вида n = p × q × r (три различных простых) имеет ровно 8 делителей.
Важно: каждый простой множитель должен входить ровно в первой степени. Число 12 = 2² × 3 не подходит, так как 2 входит в степени 2.
Стратегия решения:
Для каждого числа n в диапазоне выполняем разложение на простые множители и проверяем:
- Количество различных простых равно требуемому (2 или 3)
- Каждый простой входит в первой степени
- Выполняется дополнительное условие (например, одинаковые последние цифры)
При разложении числа n достаточно перебирать делители до √n. Если найден делитель d, то n/d — парный делитель. Для проверки, что d входит ровно один раз, убеждаемся, что (n/d) не делится на d.
ТИП 3: Числа специального вида (степени с условиями)
Формулировка: «Найти числа вида 2^m × 3^n, где m нечётное, n чётное»
Теоретическая основа:
Числа такого вида содержат в разложении только простые 2 и 3. Условия на чётность показателей резко ограничивают количество кандидатов.
Стратегия решения:
Вместо перебора всех чисел в диапазоне перебираем пары показателей (m, n):
- m пробегает нечётные значения: 1, 3, 5, 7, ...
- n пробегает чётные значения: 0, 2, 4, 6, ...
- Для каждой пары вычисляем N = 2^m × 3^n и проверяем попадание в диапазон
Количество итераций: порядка log₂(B) × log₃(B), что составляет несколько сотен вместо сотен миллионов.