Что спрашивают

R — сумма всех различных натуральных делителей числа, включая 1 и само число. Найдите первые пять чисел строго больше A, для которых R оканчивается на 6. В ответе выводятся число и его сумма делителей.

Здесь правило отличается от суммы крайних нетривиальных делителей: исключать единицу и само число нельзя. Квадратный корень, если он целый, учитывается только один раз.

Приём решения

Для каждого делителя d не больше квадратного корня добавим пару d и n // d. Эти значения покрывают все делители. Если они совпадают, добавляем только один из них — иначе квадратный корень будет посчитан дважды.

  1. Начните внутренний перебор с d = 1, чтобы учесть пару 1 и n.
  2. Проверяйте d до isqrt(n) включительно.
  3. На каждом делителе добавляйте d, затем вторую сторону пары, только если она отличается.
  4. Для полного результата проверьте R % 10 == 6.
  5. Во внешнем цикле начните с 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Последняя цифра
221, 2, 11, 22366
281, 2, 4, 7, 14, 28566
361, 2, 3, 4, 6, 9, 12, 18, 36911
391, 3, 13, 39566
421, 2, 3, 6, 7, 14, 21, 42966
621, 2, 31, 62966

После 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)
#include <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. Последняя цифра найденного числа может быть другой.