Что спрашивают
Перебирайте числа строго больше A и найдите первые пять, имеющие делитель по маске 3*2?. Для каждого числа выведите наименьший подходящий делитель. Само число тоже может выступать делителем.
В маске первая цифра 3, предпоследняя 2, последняя произвольная, между ними может быть пустая или непустая последовательность. A не больше 10^9; требуемые пять чисел существуют.
Приём решения
Если d делит n, то второй делитель пары равен n // d. У любой пары хотя бы один элемент не больше квадратного корня. Поэтому достаточно перебрать d от 1 до isqrt(n) включительно и проверить обе стороны каждой найденной пары.
Маска относится именно к делителю. Число n может не начинаться с 3 и не иметь предпоследнюю цифру 2. Для натуральной десятичной записи проверка маски сводится к трём условиям: длина не меньше трёх, первый символ 3 и предпоследний 2.
- Начните внешний перебор с A + 1.
- Для каждого n найдите минимальный подходящий элемент среди всех пар делителей.
- Если он есть, добавьте пару «n, делитель» в ответ.
- Закончите после пяти строк.
Первый найденный при переборе d подходящий большой делитель не обязательно минимален среди всех кандидатов. Поэтому сохраняем минимум до конца проверки n. Делитель n находится в паре с единицей, её пропускать нельзя.
Проверка одного числа занимает O(√n) времени и постоянную память. Все кратные 320 подходят, поэтому пять ответов появятся не позже A + 1600; это также объясняет конечность поиска на заданной области.
Разбор на примере
Ввод
635
Вывод
640 320 642 321 644 322 646 323 648 324
| Число | Найденная пара | Кандидат по маске |
|---|---|---|
| 640 | 2 и 320 | 320 |
| 642 | 2 и 321 | 321 |
| 644 | 2 и 322 | 322 |
| 646 | 2 и 323 | 323 |
| 648 | 2 и 324 | 324 |
На этом участке числа 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)
<iostream>
<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 тоже нужно проверять.
- Взять первый или самый большой кандидат
Требуется минимум среди всех подходящих делителей. Порядок появления элементов разных пар его не гарантирует.