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

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

В маске первая цифра 3, предпоследняя 2, последняя произвольная, между ними может быть пустая или непустая последовательность. A не больше 10^9; требуемые пять чисел существуют.

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

Если d делит n, то второй делитель пары равен n // d. У любой пары хотя бы один элемент не больше квадратного корня. Поэтому достаточно перебрать d от 1 до isqrt(n) включительно и проверить обе стороны каждой найденной пары.

Маска относится именно к делителю. Число n может не начинаться с 3 и не иметь предпоследнюю цифру 2. Для натуральной десятичной записи проверка маски сводится к трём условиям: длина не меньше трёх, первый символ 3 и предпоследний 2.

  1. Начните внешний перебор с A + 1.
  2. Для каждого n найдите минимальный подходящий элемент среди всех пар делителей.
  3. Если он есть, добавьте пару «n, делитель» в ответ.
  4. Закончите после пяти строк.

Первый найденный при переборе d подходящий большой делитель не обязательно минимален среди всех кандидатов. Поэтому сохраняем минимум до конца проверки n. Делитель n находится в паре с единицей, её пропускать нельзя.

Проверка одного числа занимает O(√n) времени и постоянную память. Все кратные 320 подходят, поэтому пять ответов появятся не позже A + 1600; это также объясняет конечность поиска на заданной области.

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

Ввод

635

Вывод

640 320
642 321
644 322
646 323
648 324
Разбор примера по шагам
ЧислоНайденная параКандидат по маске
6402 и 320320
6422 и 321321
6442 и 322322
6462 и 323323
6482 и 324324

На этом участке числа 640, 642, 644, 646 и 648 имеют подходящие делители 320–324. Они больше квадратного корня, поэтому проверка только маленькой стороны пары потеряла бы их. Сами найденные числа маске не соответствуют — условие этого и не требует.

Код на Python и C++

isqrt даёт точную целую границу. Квадратный корень включён; повторная проверка одного значения у квадрата не влияет на выбор минимума.

В C++ граница цикла записана как d * d <= n: корень не нужен, и погрешность sqrt не сдвинет границу. Вместо None — значение -1, вместо n // d — n / d.

import sys
from math import isqrt


def matches(n):
    text = str(n)
    return len(text) >= 3 and text[0] == '3' and text[-2] == '2'


def divisor(n):
    best = None
    for d in range(1, isqrt(n) + 1):
        if n % d == 0:
            for candidate in (d, n // d):
                if matches(candidate):
                    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>
#include <string>
using namespace std;

bool matches(long long n) {
    string text = to_string(n);
    return text.size() >= 3 && text[0] == '3' && text[text.size() - 2] == '2';
}

long long divisor(long long n) {
    long long best = -1;
    for (long long d = 1; d * d <= n; d++) {
        if (n % d == 0) {
            for (long long candidate : {d, n / d}) {
                if (matches(candidate) && (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;
        }
    }
}

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

  • Применить маску к самому числу

    Маске должен соответствовать делитель. Например, число 640 подходит благодаря делителю 320.

  • Исключить само число из делителей

    В этой задаче оно разрешено. Перебор начинается с единицы, чтобы рассмотреть пару 1 и n.

  • Проверить только делители до корня

    Ограничение до корня относится к перебираемому d. Вторую сторону n // d тоже нужно проверять.

  • Взять первый или самый большой кандидат

    Требуется минимум среди всех подходящих делителей. Порядок появления элементов разных пар его не гарантирует.