Что спрашивают
Пусть M — сумма минимального и максимального делителей числа, отличных от 1 и самого числа. Если их нет, M равна нулю. Если делитель один, он является и минимумом, и максимумом, поэтому складывается сам с собой.
Найдите первые пять чисел строго больше A, для которых M оканчивается на 4. Для каждого выведите само число и M. Входная граница A не больше 10^9.
Приём решения
Найдём первый делитель d от 2 до квадратного корня n включительно. Это наименьший нетривиальный делитель. Тогда наибольший нетривиальный делитель равен n // d: чем меньше одна сторона пары, тем больше другая.
- Если n не больше трёх, нетривиальных делителей нет.
- Для чётного составного n сразу получите
2 + n // 2. - Для нечётного n перебирайте нечётные d от трёх до isqrt(n).
- На первом делителе верните
d + n // d; если его нет, верните ноль. - Во внешнем цикле проверяйте
M % 10 == 4, начиная с A + 1.
У квадрата простого обе стороны первой пары совпадают. Например, для 49 получаем 7 + 7 = 14, а не 7. Это сумма двух характеристик — минимума и максимума, а не сумма разных элементов множества делителей.
Каждая функция значения работает за O(√n) в худшем случае и завершает поиск раньше при обнаружении первого делителя. Память состояния постоянна. Внешний цикл идёт по числам по возрастанию и останавливается только после пяти подходящих.
Разбор на примере
Ввод
45
Вывод
49 14 63 24 64 34 84 44 93 34
| Число | Минимальный | Максимальный | M |
|---|---|---|---|
| 47 | Нет | Нет | 0 |
| 49 | 7 | 7 | 14 |
| 63 | 3 | 21 | 24 |
| 64 | 2 | 32 | 34 |
| 84 | 2 | 42 | 44 |
| 93 | 3 | 31 | 34 |
Простое 47 даёт ноль и не проходит условие. У 49 единственный нетривиальный делитель 7, но M равна 14. Дальше подходят 63, 64, 84 и 93. Значения M не обязаны возрастать: сортируется последовательность найденных чисел.
Код на Python и C++
Ноль для простого числа не удовлетворяет последней цифре 4. При квадрате простого делитель на границе корня обязательно попадает в перебор.
В C++ нечётные делители перебирает цикл for (d = 3; d * d <= n; d += 2), а n // d записывается как n / d.
import sys
from math import isqrt
def value(n):
if n <= 3:
return 0
if n % 2 == 0:
return 2 + n // 2
for d in range(3, isqrt(n) + 1, 2):
if n % d == 0:
return d + n // d
return 0
def solve(a, count=5):
rows = []
n = a + 1
while len(rows) < count:
m = value(n)
if m % 10 == 4:
rows.append((n, m))
n += 1
return rows
if __name__ == '__main__':
a = int(sys.stdin.read())
rows = solve(a)
for row in rows:
print(*row)
<iostream>
using namespace std;
long long value(long long n) {
if (n <= 3)
return 0;
if (n % 2 == 0)
return 2 + n / 2;
for (long long d = 3; d * d <= n; d += 2) {
if (n % d == 0)
return d + n / d;
}
return 0;
}
int main() {
long long a;
cin >> a;
int found = 0;
for (long long n = a + 1; found < 5; n++) {
long long m = value(n);
if (m % 10 == 4) {
cout << n << ' ' << m << '\n';
found += 1;
}
}
}
Типичные ошибки
- Добавить единицу и само число
Они явно исключены из определения M. Начальный делитель для этой функции — 2.
- Учесть единственный делитель один раз
Минимум и максимум могут совпасть, но оба входят в сумму. Для квадрата простого результат равен удвоенному корню.
- Не включить квадратный корень
У квадрата простого это единственный нетривиальный делитель. Верхняя граница range должна включать isqrt(n).
- Начать внешний цикл с A
Здесь ищутся числа строго больше границы. Начинайте с A + 1 даже при подходящем свойстве самой границы.