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

Пусть M — сумма минимального и максимального делителей числа, отличных от 1 и самого числа. Если их нет, M равна нулю. Если делитель один, он является и минимумом, и максимумом, поэтому складывается сам с собой.

Найдите первые пять чисел строго больше A, для которых M оканчивается на 4. Для каждого выведите само число и M. Входная граница A не больше 10^9.

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

Найдём первый делитель d от 2 до квадратного корня n включительно. Это наименьший нетривиальный делитель. Тогда наибольший нетривиальный делитель равен n // d: чем меньше одна сторона пары, тем больше другая.

  1. Если n не больше трёх, нетривиальных делителей нет.
  2. Для чётного составного n сразу получите 2 + n // 2.
  3. Для нечётного n перебирайте нечётные d от трёх до isqrt(n).
  4. На первом делителе верните d + n // d; если его нет, верните ноль.
  5. Во внешнем цикле проверяйте 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
497714
6332124
6423234
8424244
9333134

Простое 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)
#include <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 даже при подходящем свойстве самой границы.