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

Нужно найти первые пять чисел строго больше 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 по порядку; это сокращение выведено из условия, а не взято как произвольный предел.

  1. Начните с первого нечётного n строго после A: 26m чётно, а 3^k нечётно при любом k, поэтому n нечётно.
  2. Пропустите n, если в его записи есть 0.
  3. Проверьте степени 3, 9, 27 по возрастанию и возьмите первый допустимый показатель.
  4. Двигайтесь по нечётным числам, пока не найдены пять ответов.

На кандидата приходится три арифметические проверки и просмотр его десятичной записи. Память состояния мала и не зависит от числа просмотренных кандидатов. Выходные числа могут превышать верхнюю границу допустимого A: нельзя завершать поиск на миллионе.

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

Ввод

100

Вывод

113 2
131 3
133 1
139 2
157 3
Разбор примера по шагам
КандидатПредставлениеОтбор
10526 × 3 + 27Есть 0: пропускаем
10726 × 4 + 3Есть 0: пропускаем
11326 × 4 + 9k = 2
13126 × 4 + 27k = 3
13326 × 5 + 3 = 26 × 2 + 81Берём k = 1, а не 4
13926 × 5 + 9k = 2
15726 × 5 + 27k = 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)
#include <iostream>
#include <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.

  • Сохранить последний найденный показатель

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

  • Забыть запрет нуля в записи

    Арифметическое представление само по себе недостаточно. Проверка цифр — отдельное условие отбора.