Что спрашивают
Нужно найти первые пять чисел строго больше A, имеющих делитель, оканчивающийся на 11. Подходящий делитель должен отличаться и от самого числа, и от числа 11. Для каждого ответа выводится наименьший такой делитель.
Проверки «последние цифры — 11» недостаточно: она сама по себе разрешает оба исключённых случая. A не превосходит 10^9, нужные пять чисел существуют.
Приём решения
Делители снова ищутся парами до корня. Можно начать с d = 2, поскольку единица не имеет нужного окончания, а само n запрещено. Для каждой пары проверим оба элемента: нужный делитель может оказаться больше корня.
- Для найденного делителя candidate проверьте
candidate % 100 == 11. - Дополнительно потребуйте
candidate != 11иcandidate != n. - Сохраните минимум среди всех прошедших проверку элементов.
- Начните внешний поиск с A + 1 и закончите после пяти чисел.
Проверка окончания через остаток от деления не зависит от длины записи. У числа 822 делитель 411 подходит, хотя он большой, а само 822 на 11 не оканчивается. Первым встретившимся подходящим значением ограничиваться нельзя: порядок перебора маленьких делителей не сортирует большие стороны пар.
Внутренняя проверка занимает O(√n) времени и постоянную память. Все кратные 111, кроме самого 111, имеют разрешённый делитель 111. Пять кратных, выбранных строго после A и самого 111, гарантируют конечность внешнего поиска.
Разбор на примере
Ввод
700
Вывод
777 111 822 411 844 211 888 111 933 311
| Число | Проверяемый делитель | Решение |
|---|---|---|
| 711 | 711 | Само число: запрещено |
| 777 | 111 | Подходит |
| 822 | 411 | Подходит, больше корня |
| 844 | 211 | Подходит |
| 888 | 111 | Минимальный подходит |
| 933 | 311 | Подходит |
Запись 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)
<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.
- Вернуть максимальный кандидат
В ответе нужен минимальный делитель с указанными свойствами. Сохраняйте минимум по всем парам.