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

Нужно найти первые пять чисел строго больше A, имеющих делитель, оканчивающийся на 11. Подходящий делитель должен отличаться и от самого числа, и от числа 11. Для каждого ответа выводится наименьший такой делитель.

Проверки «последние цифры — 11» недостаточно: она сама по себе разрешает оба исключённых случая. A не превосходит 10^9, нужные пять чисел существуют.

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

Делители снова ищутся парами до корня. Можно начать с d = 2, поскольку единица не имеет нужного окончания, а само n запрещено. Для каждой пары проверим оба элемента: нужный делитель может оказаться больше корня.

  1. Для найденного делителя candidate проверьте candidate % 100 == 11.
  2. Дополнительно потребуйте candidate != 11 и candidate != n.
  3. Сохраните минимум среди всех прошедших проверку элементов.
  4. Начните внешний поиск с A + 1 и закончите после пяти чисел.

Проверка окончания через остаток от деления не зависит от длины записи. У числа 822 делитель 411 подходит, хотя он большой, а само 822 на 11 не оканчивается. Первым встретившимся подходящим значением ограничиваться нельзя: порядок перебора маленьких делителей не сортирует большие стороны пар.

Внутренняя проверка занимает O(√n) времени и постоянную память. Все кратные 111, кроме самого 111, имеют разрешённый делитель 111. Пять кратных, выбранных строго после A и самого 111, гарантируют конечность внешнего поиска.

Разбор на примере

Ввод

700

Вывод

777 111
822 411
844 211
888 111
933 311
Разбор примера по шагам
ЧислоПроверяемый делительРешение
711711Само число: запрещено
777111Подходит
822411Подходит, больше корня
844211Подходит
888111Минимальный подходит
933311Подходит

Запись 711 оканчивается на 11, но это не разрешает использовать её как делитель самой себя. Первое подходящее число после 700 — 777. Для 822 и 844 нужны большие стороны пар. Ответ упорядочен по найденным числам, а не по значениям делителей.

Код на Python и C++

Оба исключения оставлены в условии явно. Корень включён в перебор: у квадрата единственный подходящий делитель может находиться именно там.

В C++ оба элемента пары перебирает цикл for (long long candidate : {d, n / d}), отсутствие делителя обозначено значением -1.

import sys
from math import isqrt


def divisor(n):
    best = None
    for d in range(2, isqrt(n) + 1):
        if n % d == 0:
            for candidate in (d, n // d):
                if candidate != n and candidate != 11 and candidate % 100 == 11:
                    if best is None or candidate < best:
                        best = candidate
    return best


def solve(a, count=5):
    rows = []
    n = a + 1
    while len(rows) < count:
        d = divisor(n)
        if d is not None:
            rows.append((n, d))
        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(long long n) {
    long long best = -1;
    for (long long d = 2; d * d <= n; d++) {
        if (n % d == 0) {
            for (long long candidate : {d, n / d}) {
                if (candidate != n && candidate != 11 && candidate % 100 == 11) {
                    if (best == -1 || candidate < best)
                        best = candidate;
                }
            }
        }
    }
    return best;
}

int main() {
    long long a;
    cin >> a;
    int found = 0;
    for (long long n = a + 1; found < 5; n++) {
        long long d = divisor(n);
        if (d != -1) {
            cout << n << ' ' << d << '\n';
            found += 1;
        }
    }
}

Типичные ошибки

  • Разрешить делитель 11

    Он имеет нужное окончание, но отдельно исключён условием. Эта проверка должна выполняться дополнительно.

  • Использовать само число

    У числа с окончанием 11 всё равно должен существовать другой разрешённый делитель.

  • Забыть большую сторону пары

    Делители 411 и 211 в примере превышают корни своих чисел. Проверяются и d, и n // d.

  • Вернуть максимальный кандидат

    В ответе нужен минимальный делитель с указанными свойствами. Сохраняйте минимум по всем парам.