Что спрашивают
Нужно найти первые пять чисел строго больше A без цифры 0, представимых в виде n = 26m + 3^k, где m и k — натуральные. При нескольких представлениях выбирается наименьший k.
Множитель 26 возникает из требования «чётное положительное число, кратное 13». Первое слагаемое не может быть нулём, показатель начинается с единицы. Входное A не больше 10^6.
Приём решения
Для фиксированного k проверьте два условия: n > 3^k и (n - 3^k) % 26 == 0. Первое обеспечивает положительность m, второе — нужную кратность. Начинать с k = 0 нельзя.
Число 3³ равно 27, то есть даёт остаток 1 при делении на 26. Поэтому 3^(k+3) - 3^k = 26 × 3^k. Если представление существует с показателем k + 3, его можно переписать с показателем k, увеличив m на положительное 3^k.
Повторяя уменьшение показателя, получаем один из k = 1, 2, 3. Следовательно, минимальный показатель всегда входит в эту тройку. Проверять достаточно степени 3, 9, 27 по порядку; это сокращение выведено из условия, а не взято как произвольный предел.
- Начните с первого нечётного n строго после A:
26mчётно, а3^kнечётно при любом k, поэтому n нечётно. - Пропустите n, если в его записи есть 0.
- Проверьте степени 3, 9, 27 по возрастанию и возьмите первый допустимый показатель.
- Двигайтесь по нечётным числам, пока не найдены пять ответов.
На кандидата приходится три арифметические проверки и просмотр его десятичной записи. Память состояния мала и не зависит от числа просмотренных кандидатов. Выходные числа могут превышать верхнюю границу допустимого A: нельзя завершать поиск на миллионе.
Разбор на примере
Ввод
100
Вывод
113 2 131 3 133 1 139 2 157 3
| Кандидат | Представление | Отбор |
|---|---|---|
| 105 | 26 × 3 + 27 | Есть 0: пропускаем |
| 107 | 26 × 4 + 3 | Есть 0: пропускаем |
| 113 | 26 × 4 + 9 | k = 2 |
| 131 | 26 × 4 + 27 | k = 3 |
| 133 | 26 × 5 + 3 = 26 × 2 + 81 | Берём k = 1, а не 4 |
| 139 | 26 × 5 + 9 | k = 2 |
| 157 | 26 × 5 + 27 | k = 3 |
Числа 105 и 107 имеют нужные представления, но содержат запрещённый ноль. Первым проходит 113. Для 133 существуют показатели 1 и 4; минимальный равен 1. Пять найденных пар выводятся в порядке чисел: 113, 131, 133, 139, 157.
Код на Python и C++
Условие n > power исключает нулевое первое слагаемое. Ограничение проверки тремя показателями обосновано периодичностью степеней по модулю 26.
В C++ ноль в записи ищет to_string(n).find('0'), а степени тройки получаются умножением в цикле.
import sys
def minimum_exponent(n):
for k, power in enumerate((3, 9, 27), start=1):
if n > power and (n - power) % 26 == 0:
return k
return None
def solve(a, count=5):
rows = []
n = a + 1
if n % 2 == 0:
n += 1
while len(rows) < count:
if '0' not in str(n):
k = minimum_exponent(n)
if k is not None:
rows.append((n, k))
n += 2
return rows
if __name__ == '__main__':
a = int(sys.stdin.read())
rows = solve(a)
for row in rows:
print(*row)
<iostream>
<string>
using namespace std;
int minimum_exponent(long long n) {
long long power = 1;
for (int k = 1; k <= 3; k++) {
power *= 3;
if (n > power && (n - power) % 26 == 0)
return k;
}
return -1;
}
int main() {
long long a;
cin >> a;
long long n = a + 1;
if (n % 2 == 0)
n += 1;
int found = 0;
while (found < 5) {
if (to_string(n).find('0') == string::npos) {
int k = minimum_exponent(n);
if (k != -1) {
cout << n << ' ' << k << '\n';
found += 1;
}
}
n += 2;
}
}
Типичные ошибки
- Разрешить нулевое первое слагаемое
Само число 27 не подходит как 0 + 3³: m должно быть положительным. Проверяйте строгое n > power.
- Начать показатель с нуля
Натуральный показатель здесь начинается с единицы. Степень 3⁰ не входит в разрешённые представления.
- Проверить кратность только 13
Первое слагаемое ещё и чётное. Обе характеристики вместе дают положительную кратность 26.
- Сохранить последний найденный показатель
Требуется минимум. Проверяйте показатели по возрастанию и завершайте выбор на первом подходящем.
- Забыть запрет нуля в записи
Арифметическое представление само по себе недостаточно. Проверка цифр — отдельное условие отбора.