At the recent IZhO in mathematics there were unusual problems, many of which trolled the majority of participants. P2 was solved by a trick, and many failed to find it. I also did not solve it: during the contest I acted too technically, which did not help. My approach was an attempt to squeeze the desired number between given ones, which is a stronger statement (but, as it turned out, equivalent) that I managed to prove after the contest.

Problem.

Let $$$n$$$ be a positive integer for which there exist positive integers $$$a$$$ and $$$b$$$ such that

Prove that there exists a positive integer $$$c$$$ such that

Official solution

Denote

Adding, we obtain

from which

My solution

Idea.

1. We look for values $$$x_c$$$ that are squeezed between $$$a\sqrt{10}$$$ and $$$b\sqrt{11}$$$;
2. we prove that such a $$$c$$$ exists and is unique;
3. we show that for the remaining $$$c$$$ equality of integer parts is impossible.

Denote

Step 1. Squeezing condition

If

then it immediately follows that

This is equivalent to the inequality

Compute the differences:

Since the denominator is positive, we obtain the equivalent condition

Hence,

where

Step 2. Uniqueness of the integer solution

The length of the segment equals

From the conditions we have

therefore

Thus, at most one integer can lie in $$$[L, R]$$$.

At the same time,

from which

Therefore,

is the unique integer solution; the necessary and sufficient conditions are verified.

Step 3. Absence of other solutions

From the inequality $$$b\sqrt{11} - a\sqrt{10} \lt 1$$$ it follows that

Then

Consequently,

that is,

Similarly,

Hence, no other values of $$$c$$$ exist.

G. Modular Tetration — a Number Theory Solution

Preliminary Comments

I deleted the first post and am publishing a new one with preliminary comments. This problem turned out to be problematic and spoiled the contest for strong participants, since some cheaters copied it, but it didn’t seem difficult to me, except for deriving the final formula and a bit of implementation. During the contest, I managed to work out the implementation on paper, but I couldn’t handle the coding.

I am a junior in mathematics, focusing on number theory and algebra (at the last JBMO I managed to solve both of these topics), but I still have many gaps in CP and implementation. In number theory I solve or make substantial progress on many problems from IMO shortlists. If you assign a CF-like rating to those problems, I solve problems steadily up to 2000, sometimes up to 2500, and there have been harder ones.

Now I want to use number theory and mathematical implementation of programming problems as a boost for CP. I noticed that the mathematical part of some problems (above my current rating) is easy for me, which gives me hope to raise both implementation and CP methods to the same level. For example, in the summer I solved the “Faculty” (2400) number theory problem on my own within an hour. I implemented the mathematical part and managed to write the code.

On paper I analyze CP problems rated 2000 and higher, where I can use my mathematical skills. I started publishing some materials on my blog. Most often I fail to write code for these problems, but if I have a solution on paper, everything else is psychologically easier to study, learn new things and thus grow. The main thing is not the solution itself, but the path. I also use this tactic — if I have a solution, I write a naive TLE code, then improve it; even if the code passes, I try to improve the time further to understand all the techniques.

That was the introduction. Below is my write-up for problem 2147G, which I was able to solve on paper in 30 minutes (though there are still unclear points), but I still can’t implement the code. Such a solution is natural for mathematicians; all steps are clear to anyone who has studied olympiad number theory even at a basic level. But the official editorial is not very clear to me — that is, it is clear, but unfamiliar. It is more suitable for experienced CP programmers. Perhaps I am wrong.

Write-up

Let $$$m\ge 2$$$ be given, and define the sequence $$${b_n}$$$ by

Call $$$a$$$ $$$m$$$-tetrated if there exists $$$N$$$ such that

We need the density of such $$$a$$$.

1) Euler

By Euler’s theorem:

By the requirement, $$$a^{b_n}\equiv1\pmod m$$$ for all $$$n\ge N$$$. It is then obvious that $$$(a,m)=1$$$; otherwise the residue $$$1$$$ won’t appear.

2) $$$\gcd$$$ trick (Euclid)

Classical fact: if $$$a^r\equiv1\pmod m$$$ and $$$a^s\equiv1\pmod m$$$, then

(Proof via Bézout: $$$\gcd(r,s)=ur+vs$$$.)

Hence,

This is a classical trick for this type of problems.

3) Order $$$d=\mathrm{ord}_m(a)$$$

Introduce

Then

Also $$$b_{n+1}=a^{b_n}$$$, hence every prime divisor of $$$d$$$ must divide $$$a$$$. I think these are necessary and sufficient conditions for $$$b_n\equiv1\pmod m$$$ starting from some $$$N$$$. We have reformulated the problem in a convenient way without losing equivalence. Introducing $$$\mathrm{ord}$$$ here plays the same role as, for example, considering the least prime divisor or introducing $$$\gcd$$$. That is, we introduce an extra variable, but the constraints become very tight.

4) Chinese Remainder Theorem (reduction to prime powers)

Divide and conquer. Write $$$m=\prod p^{\alpha}$$$. The condition modulo $$$m$$$ is equivalent to the system modulo all $$$p^{\alpha}$$$. If $$$p^{\alpha}\mid m$$$, repeat the reasoning from items 1–3 for $$$p^{\alpha}$$$. Similarly we get that every prime divisor of $$$d_p$$$ must divide $$$a$$$. Note that

but $$$(a,p)=1 \Rightarrow d_p \mid (p-1)$$$. Thus, every prime divisor of $$$d_p$$$ (which, in turn, divides $$$p$$$) must be a divisor of $$$a$$$.

5) Density over primes

For example, when $$$p=2$$$: $$$d_2=1 \Rightarrow a\equiv1\pmod{2^{\,\alpha}}$$$ $$$\Rightarrow$$$ we get a contribution $$$1/2^{\,\alpha}$$$.

Similarly, for $$$p \gt 2$$$ we get the contribution $$$\varphi(d_p)/p^{\alpha}$$$, where $$$d_p$$$ is taken among divisors of $$$p-1$$$. There are a couple more nuances needed to derive the exact final formula.

6) Implementation

Implementation in progress :-))

Introducing gcd: sacrifice one variable to gain tight constraints

In problems with two (or more) integer variables it’s often profitable to factor out their gcd: let $$$d=\gcd(x,y)$$$, then write $$$x=a d,\ y=b d$$$ with $$$\gcd(a,b)=1$$$. Sure, you’ve added one more variable ($$$d$$$), but in exchange you get the coprimality of $$$a,b$$$, which sharply restricts the search space, makes divisibility statements “split” into clean factors, and simplifies the final casework/estimates.

How to apply (6-step template)

1. Normalize. Handle zeros/signs first (e.g., consider the cases $$$x=0\leftrightarrow y=0$$$, $$$x,y \gt 0$$$, etc.).
2. Introduce gcd. Put $$$d=\gcd(x,y)$$$, set $$$x=a d,\ y=b d$$$ with $$$\gcd(a,b)=1$$$.
3. Cancel powers of $$$d$$$. Divide the original equation/divisibility by the maximal power of $$$d$$$.
4. Split divisibility. Any statement like $$$U(a,b)\mid V(a,b)$$$ with coprime pieces often forces a “big” factor to divide one rigid component.
5. Finish with tiny gcd-lemmas. Standard 1–3 line facts (by Euclid) you’ll use repeatedly:

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

1. Wrap up by checking a short list of cases/divisors. After Step 4 you typically reduce to a finite set (often divisors of a prime/nearly prime number) that’s easy to brute-check.

Four illustrative sketches

1) BMO 2017 P1

Find all positive integer pairs $$$(x,y)$$$ such that

Move: $$$x=ad,\ y=bd,\ \gcd(a,b)=1$$$. Then

Hence

But $$$\gcd\big(ab,\ a^2-ab+b^2\big)=1$$$ (see lemmas), so $$$a^2-ab+b^2\mid 43$$$. Thus $$$a^2-ab+b^2\in{1,43}$$$ — finish by a short brute force (squares grow fast).

2) JBMO SL 2019 N3

Find all primes $$$p$$$ and non-negative integers $$$x\neq y$$$ such that

Move: $$$x=ad,\ y=bd,\ \gcd(a,b)=1$$$. Then

By the lemmas, $$$\gcd\big((a+b)(a^2+b^2),\ a^2+ab+b^2\big)=1$$$. Hence $$$(a+b)(a^2+b^2)\mid p$$$, impossible for a prime $$$p$$$ when $$$a,b \gt 0$$$. Conclusion: one of $$$x,y$$$ is zero $$$\Rightarrow (x,y)=(0,p),(p,0)$$$.

3) JBMO SL 2021 N5

Find all integer solutions of $$$x^2+5y^2=2021y$$$.

Move: first note $$$x=0\iff y=0$$$. Then assume $$$x \gt 0\Rightarrow y \gt 0$$$. Put $$$x=ad,\ y=bd,\ \gcd(a,b)=1$$$. We get

Since $$$\gcd(a^2+5b^2,\ b)=1$$$, it follows that $$$a^2+5b^2\mid 2021$$$. (Factor 2021 and finish with a short divisor check.)

4) JBMO 2018 P1

Find all integers $$$m,n$$$ with $$$m^5-n^5=16mn$$$.

Move: $$$m=0\iff n=0$$$. For $$$mn\neq0$$$: $$$m=ad,\ n=bd,\ \gcd(a,b)=1$$$.

By the lemma $$$\gcd(a^5-b^5,\ ab)=1$$$, hence $$$a^5-b^5\mid16$$$. Finish by checking the divisors of 16.

When this gcd-trick almost surely shines

• Symmetric polynomials in $$$x,y$$$ with the “classic” blocks $$$a^2\pm ab+b^2$$$, $$$a^m\pm b^m$$$.
• Equations/divisibilities where, after canceling $$$d$$$, a rigid coprime factor appears.
• gcd/lcm couplings (“given gcd and lcm”, “gcd divides/is multiple of …”, etc.).
• “Optimize distance with fixed $$$\gcd$$$”: $$$A=G\cdot u$$$, $$$B=G\cdot v$$$, $$$\gcd(u,v)=1$$$.

Mini-lemma library (all 1–3 lines via Euclid)

• $$$\gcd(a^2+b^2,\ ab)=\gcd(a^2-b^2,\ ab)=1$$$ for $$$\gcd(a,b)=1$$$.
• $$$\gcd(a+b,\ a^2-ab+b^2)=\gcd(a+b,\ 3ab)$$$. With $$$\gcd(a,b)=1$$$ and $$$a+b$$$ not divisible by $$$a$$$ or $$$b$$$, this equals 1 or 3.
• $$$\gcd(a^m-b^m,\ a)=\gcd(b^m,\ a)=1$$$ for all $$$m$$$ when $$$\gcd(a,b)=1$$$; similarly for $$$b$$$.

CP tasks where “factor out the gcd” fits naturally

Codeforces

• 1967B1 — Reverse Card (Easy): condition “ $$$a+b$$$ is a multiple of $$$b\cdot\gcd(a,b)$$$”. Set $$$a=du,\ b=dv,\ \gcd(u,v)=1$$$ and reduce to divisors/constraints on $$$u,v$$$. (Codeforces)
• 1967B2 — Reverse Card (Hard): same structure with inverted divisibility; technique is the same, but watch the bounds. (Codeforces)
• 992B — Nastya and an Array of GCDs (count pairs with given $$$\gcd$$$ and $$$\mathrm{lcm}$$$): write $$$a=gx,\ b=gy$$$, $$$\gcd(x,y)=1$$$, with $$$xy=\frac{\mathrm{lcm}}{g}$$$. Then enumerate divisors. (Codeforces)
• 1617B — GCD Problem (find $$$a,b,c$$$ with $$$\gcd(a,b)=c$$$ and $$$a+b+c=n$$$): take $$$a=cu,\ b=cv$$$, $$$\gcd(u,v)=1$$$, reduce to $$$n-c=c(u+v)+c$$$. (Codeforces)
• 2043D — GCD Distance (maximize $$$|A-B|$$$ with $$$\gcd(A,B)=G$$$ and $$$A,B\in[l,r]$$$): set $$$A=G u,\ B=G v,\ \gcd(u,v)=1$$$ and work on $$$u,v$$$ within the rescaled interval. (Codeforces)

AtCoder

• ABC177 E — Coprime: checking pairwise/setwise coprimality via gcd and prime sieve (nice warm-up for the lemmas). (AtCoder)
• ARC124 C — LCM of GCDs: careful $$$\gcd/\mathrm{lcm}$$$ juggling over buckets; keep factoring out shared gcds and normalizing. (AtCoder)

Complexity note. After normalizing to $$$\gcd(a,b)=1$$$, the enumeration typically runs over divisors of a single integer (or a pair whose product is fixed), so it’s ~$$$O(\tau(n))$$$ or $$$O(\sqrt n)$$$. This is far faster than naive iteration over $$$x,y$$$.

Short logic

1. $$$(a_1,\dots,a_k) \gt (a_1,\dots,a_{k+1})$$$ $$$\Leftrightarrow$$$ $$$(a_1,\dots,a_k)=d\ge2$$$ and $$$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. For a multiset $$$S$$$ and $$$d\ge2$$$ let

• If $$$\operatorname{cnt}_d(S)=|S|$$$, then $$$d$$$ divides everything ⇒ you cannot create a drop with this $$$d$$$.
• Any permutation satisfies $$$f \le \max_{d\ge2,\ \operatorname{cnt}_d \lt |S|}\operatorname{cnt}_d$$$.

1. Achievability is clear (place all elements divisible by $$$d$$$ first, then any non-divisible one) ⇒

5. Why only prime powers $$$p^{\alpha_p+1}$$$ are enough

Let $$$G=\gcd(S)=\prod_{p} p^{\alpha_p}$$$ (take only primes $$$p$$$ actually occurring in $$$G$$$; for all others $$$\alpha_p=0$$$). Then:

• Any “useful” divisor $$$d$$$ that can create a drop does not divide the whole set, hence for at least one prime $$$p\mid d$$$ its exponent $$$e_p$$$ is strictly larger than the common exponent in $$$G$$$: $$$e_p\ge \alpha_p+1$$$.
• The set $$${x:\ d\mid x}$$$ is contained in $$${x:\ p^{e_p}\mid x}$$$ for any such $$$p$$$. Therefore

So composite divisors do not improve the maximum: it suffices to look at one prime power lifted exactly “one level” above the common exponent. * Converse (achievability): take $$$p$$$ with maximal $$$\operatorname{cnt}_{p^{\alpha_p+1}}(S)=c$$$. By definition $$$\alpha_p=\min v_p(x)$$$, so there exists an element with $$$v_p=\alpha_p$$$ ⇒ $$$c \lt |S|$$$. Place all $$$c$$$ numbers divisible by $$$p^{\alpha_p+1}$$$ first, then a number with $$$v_p=\alpha_p$$$. At position $$$k=c$$$ the prefix $$$\gcd$$$ drops in the $$$p$$$-adic exponent ⇒ a drop occurs.

Final (exact equality):

Remark: if $$$\gcd(S)=1$$$, then $$$\alpha_p=0$$$ for all $$$p$$$, and the formula gives $$$g(S)=\max_p \operatorname{cnt}_{p}(S)$$$ — the maximum number of elements divisible by a single prime.

Restatement

For the prefix $$$P_i=[a_1,\dots,a_i]$$$, let $$$G_i=\gcd(P_i)=\prod_p p^{\alpha_p(i)}$$$. Then

— i.e., “how many numbers in the prefix have, for some prime $$$p$$$, an exponent at least one higher than the common minimal exponent $$$\alpha_p(i)$$$ of $$$p$$$ in $G_i$”.

Examples

• $$$S={6,12,18}$$$. $$$\gcd=6=2^1\cdot 3^1$$$. $$$\operatorname{cnt}_{2^{2}}=1$$$ (only 12), $$$\operatorname{cnt}_{3^{2}}=1$$$ (only 18) ⇒ $$$g=1$$$. A permutation: $$$(12,6,18)$$$.

• $$$S={8,4,2}$$$. $$$\gcd=2$$$ ⇒ $$$\alpha_2=1$$$. $$$\operatorname{cnt}_{2^{2}}=2$$$ (8,4) ⇒ $$$g=2$$$. A permutation: $$$(8,4,2)$$$.

• $$$\gcd(S)=1$$$: e.g., $$$S={2,3,6,5}$$$. Max over primes: for 2 — two (2,6), for 3 — two (3,6), for 5 — one ⇒ $$$g=2$$$. Place $$$(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.