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.