На прошедшем IZhO по математике дали необычные задачи, многие из которых затроллили большинство участников. P2 решалась трюком, многие не справились. Я тоже не справился, во время тура действовал слишком технично, не помогло. Мое приближение было попыткой зажать искомое число между заданными, что является более сильным утверждением (но как оказалось эквивалентным), которое я смог доказать после тура.

Условие.

Пусть $$$n$$$ — положительное целое число, для которого существуют положительные целые $$$a$$$ и $$$b$$$, такие что

Доказать, что существует положительное целое число $$$c$$$, для которого

Официальное решение

Обозначим

Складывая, имеем

откуда

Мое решение

Идея.

1. ищем такие $$$x_c$$$, которые зажаты между $$$a\sqrt{10}$$$ и $$$b\sqrt{11}$$$;
2. доказываем, что такое $$$c$$$ существует и единственно;
3. показываем, что для остальных $$$c$$$ равенство целых частей невозможно.

Обозначим

Шаг 1. Условие зажатости

Если

то немедленно следует

Это эквивалентно неравенству

Вычислим разности:

Так как знаменатель положителен, получаем эквивалентное условие

Следовательно,

где

Шаг 2. Единственность целого решения

Длина отрезка равна

Из условий имеем

поэтому

Значит, в $$$[L, R]$$$ может лежать не более одного целого числа.

При этом

откуда

Следовательно,

— единственное целое решение, необходимые и достаточные условия проверили.

Шаг 3. Отсутствие других решений

Из неравенства $$$b\sqrt{11} - a\sqrt{10} \lt 1$$$ следует

Тогда

Следовательно,

то есть

Аналогично,

Значит, других значений $$$c$$$ не существует.

G. Модульная тетрация — решение через теорию чисел

Предварительные комментарии

Первую запись удалил, публикую новую с предварительными комментариями. Эта задача оказалась проблемной и испортила контест сильным участникам, поскольку некоторые читеры ее списали, но мне она не показалась сложной, кроме вывода финальной формулы и немного реализации. Во время контеста мне удалось сделать реализацию на бумаге, но с кодом я не справился.

Я юниор по математике, делаю акцент на теории чисел и алгебре (на последнем JBMO мне удалось решить обе эти темы), но пока имею много пробелов в информатике и реализации. В теории чисел решаю или существенно продвигаюсь во многих задачах из шорт-листов IMO. Если этим задачам дать схожий рейтинг, как на CF, то решаю задачи стабильно до 2000, иногда до 2500, бывали и сложнее.

Теперь я хочу использовать теорию чисел и математическую реализацию задач по информатике, как буст для CP. Я заметил, что математическая реализация некоторых задач (выше моего рейтинга) мне удается легко, что дает мне надежду подтянуть и реализацию и методы в информатике до такого же уровня. Например, летом я сам решил задачу Факультет (2400) на теорию чисел в течение часа. Реализовал математическую часть и смог написать код.

На бумаге разбираю задачи CP 2000 и выше, где могу использовать свои математические навыки. Некоторые материалы начал публиковать в свой блог. Чаще всего мне не удается написать код для этих задач, но если у меня есть решение на бумаге, остальное уже психологически проще изучать, проходить новое и таким образом расти. Главное не само решение задачи, а путь. Также я применяю такую тактику — если есть решение, то пишу наивный код на TLE, потом улучшаю, даже если код проходит, стараюсь еще улучшить время, чтобы понять все техники.

Это было вступление. Теперь ниже текст моего разбора задачи 2147G, которую я смог на бумаге решить за 30 минут (но есть еще неясные моменты), но пока не могу реализовать код. Такой разбор задачи естественен для математиков, все ходы понятны тем, кто даже на базовом уровне изучал олимпиадную теорию чисел. А вот официальный разбор мне не очень понятен, то есть понятен, но не привычен. Он скорее подходит опытным CP программистам. Возможно я ошибаюсь.

Разбор

Пусть задано $$$m\ge 2$$$, а последовательность $$${b_n}$$$ определяется

Назовём $$$a$$$ $$$m$$$-тетрированным, если $$$\exists N$$$ такое, что

Нужно найти плотность множества таких $$$a$$$.

1) Эйлер

По теореме Эйлера:

По условию, $$$a^{b_n}\equiv1\pmod m$$$ для всех $$$n\ge N$$$. При этом очевидно, что $$$(a,m)=1$$$, иначе не будет остатка $$$1$$$.

2) Трюк с $$$\gcd$$$ (Евклид)

Классический факт: если $$$a^r\equiv1\pmod m$$$ и $$$a^s\equiv1\pmod m$$$, то

(Доказательство через Безу: $$$\gcd(r,s)=ur+vs$$$.)

Значит,

Это классический трюк в такого рода задачах.

3) Порядок $$$d=\mathrm{ord}_m(a)$$$

Введём

Тогда

Также $$$b_{n+1}=a^{b_n}$$$, значит, каждый простой делитель $$$d$$$ должен делить $$$a$$$. Думаю, что это необходимые и достаточные условия для выполнения $$$b_n\equiv1\pmod m$$$, начиная с какого-то $$$N$$$. Переформулировали задачу удобным образом, не потеряли эквивалентность. Введение ord по смыслу здесь такое же, как например рассмотрение минимального простого делителя или ввод НОД. То есть появляется лишняя переменная, но зато ограничения становятся очень жесткими.

4) Китайская теорема (переход к простым степеням)

Делим и властвуем. Пишем $$$m=\prod p^{\alpha}$$$. Условие по $$$m$$$ эквивалентно условиям по всем $$$p^{\alpha}$$$. Если $$$p^{\alpha}\mid m$$$, повторяем рассуждения из пп. 1–3 для $$$p^{\alpha}$$$. Аналогично получаем, что каждый простой делитель $$$d_p$$$ должен делить $$$a$$$. Заметим, что

но $$$(a,p)=1 \Rightarrow d_p \mid (p-1)$$$. Итак, каждый простой делитель $$$d_p$$$ (который, в свою очередь, делит $$$p$$$), должен быть делителем $$$a$$$.

5) Плотность по простым

Например, при $$$p=2$$$: $$$d_2=1 \Rightarrow a\equiv1\pmod{2^{\,\alpha}}$$$ $$$\Rightarrow$$$ получаем вклад $$$1/2^{\,\alpha}$$$.

Аналогичным образом при $$$p \gt 2$$$ получаем вклад $$$\varphi(d_p)/p^{\alpha}$$$, где $$$d_p$$$ смотрим среди делителей $$$p-1$$$. Тут есть ещё пара нюансов для вывода точной итоговой формулы.

6) Реализация

Реализация в процессе :-))

«Ввод GCD»: жертва переменной ради жёстких ограничений

В задачах с двумя (или несколькими) целочисленными переменными часто выгодно «вынести» их общий делитель: пусть $$$d=\gcd(x,y)$$$, тогда $$$x=a d,\ y=b d$$$ и $$$\gcd(a,b)=1$$$. Да, переменных стало на одну больше (появился $$$d$$$), но взамен вы получили сильное условие взаимной простоты для $$$a,b$$$. Это резко сужает перебор делителей, заставляет делимости «распадаться» на простые случаи и упрощает добивание перебором/оценками.

Как применять (шаблон из 6 шагов)

1. Нормализация. Уберите нули/знаки (если нужно, рассмотрите случаи $$$x=0\leftrightarrow y=0$$$, $$$x,y \gt 0$$$ и т.п.).
2. Ввод GCD. Положите $$$d=\gcd(x,y)$$$, $$$x=a d$$$, $$$y=b d$$$, где $$$\gcd(a,b)=1$$$.
3. Сократите $$$d$$$. Поделите исходное уравнение/делимость на максимальную степень $$$d$$$.
4. Разорвите делимости. Любая делимость вида $$$U(a,b)\mid V(a,b)$$$ на взаимно-простых часто ведёт к тому, что большой множитель обязан делить один «жёсткий» фактор.
5. Добейте короткими леммами про $$$\gcd$$$. Типовые факты (доказываются по Евклиду в 1–3 шага):

• $$$\gcd(a^2+b^2,\ ab)=1$$$ при $$$\gcd(a,b)=1$$$.
• $$$\gcd(a+b,\ a^2+ab+b^2)=1$$$ при $$$\gcd(a,b)=1$$$.
• $$$\gcd(a^m-b^m,\ ab)=1$$$ при $$$\gcd(a,b)=1$$$.

1. Финишируйте перебором малых вариантов / делителей. После шага 4 обычно остаётся конечный набор значений (часто — делители простого/почти простого числа), который легко перебрать.

Четыре показательных скетча

1) BMO 2017 P1

Найти все пары положительных целых $$$(x,y)$$$, такие что

Ход: $$$x=ad,\ y=bd,\ \gcd(a,b)=1$$$. Тогда

Отсюда

Но $$$\gcd(ab,\ a^2-ab+b^2)=1$$$, значит $$$a^2-ab+b^2\mid 43$$$. Итого $$$a^2-ab+b^2\in{1,43}$$$ — дальше добивка коротким перебором (квадраты растут быстро).

2) JBMO SL 2019 N3

Найти все простые $$$p$$$ и целые неотрицательные $$$x\neq y$$$, такие что

Ход: $$$x=ad,\ y=bd,\ \gcd(a,b)=1$$$. Тогда

Проверкой лемм: $$$\gcd\big((a+b)(a^2+b^2),\ a^2+ab+b^2\big)=1$$$. Значит $$$(a+b)(a^2+b^2)\mid p$$$, что невозможно для простого $$$p$$$ при $$$a,b \gt 0$$$. Вывод: один из $$$x,y$$$ равен нулю $$$\Rightarrow (x,y)=(0,p),(p,0)$$$.

3) JBMO SL 2021 N5

Найти все целые решения $$$x^2+5y^2=2021y$$$. Ход: сначала замечаем: $$$x=0\iff y=0$$$. Далее $$$x \gt 0\Rightarrow y \gt 0$$$. Вводим $$$x=ad,\ y=bd,\ \gcd(a,b)=1$$$. Получаем

Из $$$\gcd(a^2+5b^2,\ b)=1$$$ следует $$$a^2+5b^2\mid 2021$$$ (простое разложение — дальше короткий перебор по делителям 2021).

4) JBMO 2018 P1

Найти все целые $$$m,n$$$, для которых $$$m^5-n^5=16mn$$$. Ход: $$$m=0\iff n=0$$$. При $$$mn\neq0$$$: $$$m=ad,\ n=bd,\ \gcd(a,b)=1$$$.

По лемме $$$\gcd(a^5-b^5,\ ab)=1$$$, значит $$$a^5-b^5\mid16$$$. Дальше — малый перебор по делителям $$$16$$$ и то, что разность 5 степеней растет очень быстро.

Когда почти наверняка сработает ввод GCD

• Симметричные многочлены в $$$x,y$$$ с «классическими» блоками $$$a^2\pm ab+b^2$$$, $$$a^m\pm b^m$$$.
• Уравнения/делимости, где после деления на $$$d$$$ появляется «жёсткий» взаимно-простой множитель.
• Связка gcd/lcm в условии («даны GCD и LCM, «GCD делит/кратно» и т.п.).
• Требования «минимизировать/максимизировать расстояние при фиксированном $$$\gcd$$$»: $$$A=G\cdot u$$$, $$$B=G\cdot v$$$, $$$\gcd(u,v)=1$$$.

Мини-библиотека лемм (на 1–3 строки по Евклиду)

• $$$\gcd(a^2+b^2,\ ab)=\gcd(a^2-b^2,\ ab)=1$$$ при $$$\gcd(a,b)=1$$$.
• $$$\gcd(a+b,\ a^2-ab+b^2)=\gcd(a+b,\ 3ab)$$$. При $$$\gcd(a,b)=1$$$ и $$$a+b$$$ не делится ни на $$$a$$$, ни на $$$b$$$, получаем 1 или 3.
• $$$\gcd(a^m-b^m,\ a)=\gcd(b^m,\ a)=1$$$ для всех $$$m$$$ при $$$\gcd(a,b)=1$$$; аналогично с $$$b$$$.

Задачи CP (где приём «вынести GCD» естественно заходит)

Codeforces

• 1967B1 — Reverse Card (Easy): условие « $$$a+b$$$ кратно $$$b\cdot\gcd(a,b)$$$». Кладём $$$a=du$$$, $$$b=dv$$$, $$$\gcd(u,v)=1$$$ и сводим к делителям/ограничениям на $$$u,v$$$. (Codeforces)
• 1967B2 — Reverse Card (Hard): та же структура, но инвертированная кратность; техника та же, осторожнее с оценками. (Codeforces)
• 992B — Nastya and an Array of GCDs (счёт пар с заданными $$$\gcd$$$ и $$$\mathrm{lcm}$$$): стандартно $$$a=gx,\ b=gy$$$, $$$\gcd(x,y)=1$$$, $$$xy=\frac{\mathrm{lcm}}{g}$$$. Дальше перебор делителей. (Codeforces)
• 1617B — GCD Problem (найти $$$a,b,c$$$ с $$$\gcd(a,b)=c$$$ и $$$a+b+c=n$$$): кладём $$$a=cu,\ b=cv$$$, $$$\gcd(u,v)=1$$$, остаётся разложить $$$n-c=c(u+v)+c$$$. (Codeforces)
• 2043D — GCD Distance (максимизировать $$$|A-B|$$$ при $$$\gcd(A,B)=G$$$ и $$$A,B\in[l,r]$$$): пишем $$$A=G u,\ B=G v,\ \gcd(u,v)=1$$$ и работаем уже внутри отрезка по $$$u,v$$$. (Codeforces)

AtCoder

• ABC177 E — Coprime: проверка «попарная/в совокупности взаимная простота» через gcd и просеивание простых (хорошая разминка к леммам). (AtCoder)
• ARC124 C — LCM of GCDs: аккуратная игра $$$\gcd/\mathrm{lcm}$$$ по пакетам значений; постоянно «вытаскиваем» общие делители и нормализуем. (AtCoder)

Замечания по сложности. После нормализации до $$$\gcd(a,b)=1$$$ перебор чаще всего идёт по делителям одного числа (или по паре делителей, чья композиция фиксирована), т.е. ~$$$O(\tau(n))$$$ или $$$O(\sqrt n)$$$. Это намного быстрее прямого перебора по $$$x,y$$$.

Короткая логика

1. $$$(a_1,\dots,a_k) \gt (a_1,\dots,a_{k+1})$$$ $$$\Leftrightarrow$$$ $$$(a_1,\dots,a_k)=d\ge2$$$ и $$$a_{k+1}\not\equiv0\pmod d$$$.
2. $$$f(a)=0$$$ $$$\Leftrightarrow$$$ $$$a_1=(a_1,a_2)=\cdots=(a_1,\dots,a_n)$$$ $$$\Leftrightarrow$$$ $$$a_1=(a_1,\dots,a_n)$$$.
3. Для множества $$$S$$$ и $$$d\ge2$$$ обозначим $$$\operatorname{cnt}_d(S)=\left|{\,x\in S \mid d\mid x\,}\right|$$$. Если $$$\mathrm{cnt}_d(S)=|S|$$$, то $$$d$$$ делит всё ⇒ с таким $$$d$$$ спада сделать нельзя. Любая перестановка удовлетворяет $$$f \le \max_{d\ge2,\ \mathrm{cnt}_d \lt |S|}\mathrm{cnt}_d$$$.
4. Достижимость очевидна (ставим подряд все кратные $$$d$$$, затем любой некратный) ⇒

Почему достаточно только простых степеней $$$p^{\alpha_p+1}$$$

Пусть $$$G=\gcd(S)=\prod_{p} p^{\alpha_p}$$$ (берём только простые $$$p$$$, реально встречающиеся в $$$G$$$; для остальных $$$\alpha_p=0$$$). Тогда: Любой «полезный» делитель $$$d$$$, который может обеспечить спад, не делит весь набор, значит хотя бы по одному простому $$$p\mid d$$$ его показатель $$$e_p$$$ строго больше общей степени в $$$G$$$: $$$e_p\ge \alpha_p+1$$$. Множество $$${x:\ d\mid x}$$$ содержится в $$${x:\ p^{e_p}\mid x}$$$ для любого такого $$$p$$$. Следовательно

То есть составные делители не улучшают максимум: достаточно смотреть на одну простую степень, поднятую ровно «на один этаж» относительно общей. * Обратная сторона (достижимость): берём $$$p$$$ с максимальной $$$\mathrm{cnt}_{p^{\alpha_p+1}}(S)=c$$$. По определению $$$\alpha_p=\min v_p(x)$$$, значит есть элемент со степенью ровно $$$\alpha_p$$$ ⇒ $$$c \lt |S|$$$. Ставим сначала все $$$c$$$ чисел, делящихся на $$$p^{\alpha_p+1}$$$, затем число с $$$v_p=\alpha_p$$$. На позиции $$$k=c$$$ показатель по $$$p$$$ у префиксного $$$\gcd$$$ падает ⇒ спад есть.

Итог (строгое равенство):

Замечание: если $$$\gcd(S)=1$$$, то $$$\alpha_p=0$$$ для всех $$$p$$$, и формула даёт $$$g(S)=\max_p \mathrm{cnt}_{p}(S)$$$ — максимум числа кратных одному простому.

Переформулировка

Для префикса $$$P_i=[a_1,\dots,a_i]$$$, положим $$$G_i=\gcd(P_i)=\prod_p p^{\alpha_p(i)}$$$. Тогда

— то есть «сколько чисел в префиксе имеют по простому $$$p$$$ степень хотя бы на 1 больше общей минимальной степени по этому $$$p$$$ в $G_i$».

Примеры

• $$$S={6,12,18}$$$. $$$\gcd=6=2^1\cdot 3^1$$$. $$$\mathrm{cnt}_{2^{2}}=1$$$ (только 12), $$$\mathrm{cnt}_{3^{2}}=1$$$ (только 18) ⇒ $$$g=1$$$. Перестановка: (12,6,18).

• $$$S={8,4,2}$$$. $$$\gcd=2$$$ ⇒ $$$\alpha_2=1$$$. $$$\mathrm{cnt}_{2^{2}}=2$$$ (8,4) ⇒ $$$g=2$$$. Перестановка: (8,4,2).

• $$$\gcd(S)=1$$$: например $$$S={2,3,6,5}$$$. Макс по простым: по 2 — трое (2,6), по 3 — двое (3,6), по 5 — один ⇒ $$$g=2$$$. Ставим (2,6,3,5).

Editorial: Concatenation & Divisibility (extended version of CF 2140B)

Below is a guide for solving the extended version of problem 2140B, where instead of outputting just any valid solution, we describe how to enumerate all valid integers $$$y$$$. This problem is much deeper than just printing the trivial $$$y=2x$$$.

Problem statement (recap)

We are given an integer $$$x$$$ ($$$1 \le x \lt 10^8$$$). We want to find an integer $$$y$$$ ($$$1 \le y \lt 10^9$$$) such that

and $$$k$$$ is the number of digits of $$$y$$$.

The original problem (CF 2140B) only required outputting any valid $$$y$$$. Here we discuss the structural description of all solutions and two efficient constructive algorithms.

Key equivalence

The condition is:

Let $$$d=\gcd(x,y)$$$, $$$x=ad,\ y=bd$$$. Then $$$x+y = d(a+b)$$$. The divisibility condition becomes:

Since $$$\gcd(a,a+b)=1$$$, we conclude:

Denote $$$M=a+b$$$, which is a divisor of $$$R_k = 10^k-1$$$. Then $$$x+y = dM \implies y = dM - x$$$.

Thus, all solutions are described by:

The last inequality ensures that $$$y$$$ has exactly $$$k$$$ digits. Equivalently:

Solution 1: Factorization and divisor lists

Idea. For each $$$k=1..9$$$, factorize $$$R_k=10^k-1$$$ and store all divisors in sorted arrays $$$D_k$$$. For a given $$$x$$$:

1. Factorize $$$x$$$ using primes up to $$$\sqrt{x}$$$.
2. Generate all divisors $$$d \mid x$$$.
3. For each $$$d$$$ and $$$k$$$, compute the interval for $$$M$$$.
4. Use binary search on $$$D_k$$$ to find any divisor $$$M$$$ in this interval.
5. Return $$$y = dM - x$$$.

Correctness. By construction, $$$M \mid (10^k-1)$$$ and $$$d\mid x$$$ guarantee the divisibility condition. The interval ensures that $$$y$$$ has exactly $$$k$$$ digits. Thus, every valid $$$y$$$ arises in this way.

Complexity.

• Precomputation: divisors of $$$10^k-1$$$ for $$$k\le 9$$$ (constant).
• Per test: factorization of $$$x$$$ ($$$O(\pi(\sqrt{x}))$$$) + divisor generation ($$$O(\tau(x))$$$) + binary searches ($$$O(\tau(x) \cdot 9 \cdot \log |D_k|)$$$). With early exit after the first found solution, this is very fast.

Code (C++17)

#include <bits/stdc++.h> 
using namespace std;
 
using int64 = long long;
 
vector<int> sieve_primes(int limit = 31623) {
    vector<bool> is_prime(limit + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i * i <= limit; ++i)
        if (is_prime[i])
            for (int j = i * i; j <= limit; j += i) is_prime[j] = false;
    vector<int> primes;
    for (int i = 2; i <= limit; ++i) if (is_prime[i]) primes.push_back(i);
    return primes;
}
 
vector<pair<int64,int>> factorize_ll(int64 n, const vector<int>& primes) {
    vector<pair<int64,int>> f;
    for (int p : primes) {
        if (1LL * p * p > n) break;
        if (n % p == 0) {
            int cnt = 0;
            while (n % p == 0) { n /= p; ++cnt; }
            f.push_back({p, cnt});
        }
    }
    if (n > 1) f.push_back({n, 1});
    return f;
}
 
void gen_divs(const vector<pair<int64,int>>& f, vector<int64>& divs, int idx=0, int64 cur=1) {
    if (idx == (int)f.size()) { divs.push_back(cur); return; }
    auto [p, e] = f[idx];
    for (int i = 0; i <= e; ++i) {
        gen_divs(f, divs, idx + 1, cur);
        cur *= p;
    }
}
 
vector<int64> all_divs(int64 n, const vector<int>& primes) {
    auto fac = factorize_ll(n, primes);
    vector<int64> divs;
    gen_divs(fac, divs);
    sort(divs.begin(), divs.end());
    return divs;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    const int KMAX = 9;
    const int64 LIM_Y = 1000000000LL;
    vector<int64> pow10(KMAX + 1, 1);
    for (int k = 1; k <= KMAX; ++k) pow10[k] = pow10[k - 1] * 10;
 
    vector<int> primes = sieve_primes();
 
    vector<vector<int64>> D(KMAX + 1);
    for (int k = 1; k <= KMAX; ++k) {
        D[k] = all_divs(pow10[k] - 1, primes);
    }
 
    int T; cin >> T;
    while (T--) {
        long long x; cin >> x;
        vector<int64> divx = all_divs(x, primes);
        bool found = false;
 
        for (int k = 1; k <= KMAX && !found; ++k) {
            int64 Lk = pow10[k - 1], Uk = pow10[k] - 1;
            for (int64 d : divx) {
                int64 L = (x + Lk + d - 1) / d;
                int64 U = (x + Uk) / d;
                if (L > U) continue;
                auto itL = lower_bound(D[k].begin(), D[k].end(), L);
                auto itU = upper_bound(D[k].begin(), D[k].end(), U);
                if (itL == itU) continue;
                int64 M = *itL;
                int64 y = d * M - x;
                if (y >= 1 && y < LIM_Y) {
                    cout << y << "\n";
                    found = true;
                    break;
                }
            }
        }
        if (!found) cout << 1 << "\n";
    }
}

Solution 2: Precompute divisors of $$$10^k-1$$$ directly, pure 64-bit check

Idea. Instead of factoring $$$10^k-1$$$ with primes, directly compute its divisors by iterating up to $$$\sqrt{10^k-1}$$$ for each $$$k=1..9$$$. Store sorted lists dd[k]. Then repeat the same search procedure: for each $$$d \mid x$$$, compute interval for $$$M$$$, binary search inside dd[k], and construct $$$y=dM-x$$$.

Divisibility check is done with modular arithmetic fully in 64-bit:

Since $$$(x+y) \lt 2 \cdot 10^9$$$, intermediate multiplications never overflow 64-bit.

Complexity.

• Precompute divisors of $$$10^k-1$$$: $$$O(\sum_k \sqrt{10^k})$$$ — constant for $$$k \le 9$$$.
• Per test: divisor search of $$$x$$$ ($$$O(\sqrt{x})$$$) + binary search inside dd[k] ($$$O(\tau(x) \cdot 9 \cdot \log |dd[k]|)$$$). With early exit, runs comfortably fast.

Code (C++17)

#include <bits/stdc++.h>
using namespace std;
 
int pw10[11];
vector<int> dd[11];
 
inline long long ceil_div(long long a, long long b) {
    return (a + b - 1) / b;
}
 
inline bool divisible_check(long long x, int k, long long y) {
    long long den = x + y;
    long long t1  = x % den;
    long long t2  = pw10[k] % den;
    long long lhs = (t1 * t2) % den;
    lhs = (lhs + (y % den)) % den;
    return lhs == 0;
}
 
void solve() {
    int x; cin >> x;
 
    vector<int> del;
    for (int i = 1; 1LL * i * i <= x; ++i) {
        if (x % i == 0) {
            del.push_back(i);
            if (x / i != i) del.push_back(x / i);
        }
    }
 
    for (int k = 1; k <= 9; ++k) {
        long long Lk = pw10[k - 1], Uk = 1LL * pw10[k] - 1;
        const auto &Dv = dd[k];
        for (int d : del) {
            long long L = ceil_div(1LL * x + Lk, d);
            long long U = (1LL * x + Uk) / d;
            if (L > U) continue;
            auto itL = lower_bound(Dv.begin(), Dv.end(), (int)L);
            auto itU = upper_bound(Dv.begin(), Dv.end(), (int)U);
            for (auto it = itL; it != itU; ++it) {
                long long M = *it;
                long long y = 1LL * d * M - x;
                if (y >= 1 && y < 1000000000LL && divisible_check(x,k,y)) {
                    cout << y << "\n";
                    return;
                }
            }
        }
    }
    cout << 1 << "\n";
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    pw10[0] = 1;
    for (int i = 1; i < 11; ++i) pw10[i] = pw10[i - 1] * 10;
 
    for (int k = 1; k <= 9; ++k) {
        int num = pw10[k] - 1;
        for (int j = 1; 1LL * j * j <= num; ++j) {
            if (num % j == 0) {
                dd[k].push_back(j);
                if (j != num / j) dd[k].push_back(num / j);
            }
        }
        sort(dd[k].begin(), dd[k].end());
    }
 
    int tt; cin >> tt;
    while (tt--) solve();
}

Conclusion

Both solutions rely on the structural criterion:

They differ only in how divisors of $$$10^k-1$$$ are precomputed (via prime factorization or direct sqrt scan) and in the style of the divisibility check. With early exit on the first valid $$$y$$$, both run in well under the time limit for $$$t \le 10^4$$$. If the extended problem asks for all solutions, just loop through all candidate $$$M$$$ in the interval instead of breaking at the first.