Что спрашивают
R — сумма всех различных натуральных делителей числа, включая 1 и само число. Найдите первые пять чисел строго больше A, для которых R оканчивается на 6. В ответе выводятся число и его сумма делителей.
Здесь правило отличается от суммы крайних нетривиальных делителей: исключать единицу и само число нельзя. Квадратный корень, если он целый, учитывается только один раз.
Приём решения
Для каждого делителя d не больше квадратного корня добавим пару d и n // d. Эти значения покрывают все делители. Если они совпадают, добавляем только один из них — иначе квадратный корень будет посчитан дважды.
- Начните внутренний перебор с d = 1, чтобы учесть пару 1 и n.
- Проверяйте d до isqrt(n) включительно.
- На каждом делителе добавляйте d, затем вторую сторону пары, только если она отличается.
- Для полного результата проверьте
R % 10 == 6. - Во внешнем цикле начните с A + 1 и соберите первые пять пар.
Например, у 36 пары равны (1, 36), (2, 18), (3, 12), (4, 9) и (6, 6). Сумма равна 91, а корень 6 должен войти один раз. У простого числа сумма равна 1 + n: такие числа тоже могут пройти условие последней цифры.
Проверка одного n занимает O(√n) времени, состояние — постоянную память. Более продвинутый способ использует разложение на простые степени и формулу R = (1 + p + ... + p^a) × .... В приведённом коде оставлен прямой проход по парам, чтобы явно видеть правило учёта каждого делителя.
Разбор на примере
Ввод
20
Вывод
22 36 28 56 39 56 42 96 62 96
| Число | Все делители | R | Последняя цифра |
|---|---|---|---|
| 22 | 1, 2, 11, 22 | 36 | 6 |
| 28 | 1, 2, 4, 7, 14, 28 | 56 | 6 |
| 36 | 1, 2, 3, 4, 6, 9, 12, 18, 36 | 91 | 1 |
| 39 | 1, 3, 13, 39 | 56 | 6 |
| 42 | 1, 2, 3, 6, 7, 14, 21, 42 | 96 | 6 |
| 62 | 1, 2, 31, 62 | 96 | 6 |
После A = 20 первыми проходят 22 и 28. Квадрат 36 между ними и следующими ответами не подходит: сумма 91 не оканчивается на 6. Продолжаем перебор до 39, 42 и 62. Значение суммы у разных чисел может совпадать, но каждое найденное число даёт свою строку.
Код на Python и C++
Набор делителей хранить не нужно. Каждая пара найдена один раз, а совпавшие стороны пары у квадрата разделены отдельной проверкой.
В C++ цикл идёт, пока d * d <= n, а n // d записывается как n / d.
import sys
from math import isqrt
def divisor_sum(n):
total = 0
for d in range(1, isqrt(n) + 1):
if n % d == 0:
total += d
other = n // d
if other != d:
total += other
return total
def solve(a, count=5):
rows = []
n = a + 1
while len(rows) < count:
total = divisor_sum(n)
if total % 10 == 6:
rows.append((n, total))
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 divisor_sum(long long n) {
long long total = 0;
for (long long d = 1; d * d <= n; d++) {
if (n % d == 0) {
total += d;
long long other = n / d;
if (other != d)
total += other;
}
}
return total;
}
int main() {
long long a;
cin >> a;
int found = 0;
for (long long n = a + 1; found < 5; n++) {
long long total = divisor_sum(n);
if (total % 10 == 6) {
cout << n << ' ' << total << '\n';
found += 1;
}
}
}
Типичные ошибки
- Исключить единицу или само число
Здесь они входят в сумму. Перебор с d = 1 учитывает оба элемента соответствующей пары.
- Дважды прибавить корень
У квадрата обе стороны последней пары совпадают. Вторая прибавляется только при отличии от первой.
- Проверить последнюю цифру самого n
Окончание 6 требуется от суммы R. Последняя цифра найденного числа может быть другой.