# 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 < 10^8$).↵
We want to find an integer $y$ ($1 \le y < 10^9$) such that↵
↵
$$↵
x\#y \equiv 0 \pmod{x+y}, ↵
\quad\text{where}\quad↵
x\#y = x \cdot 10^k + y,↵
$$↵
↵
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:↵
↵
$$↵
x \cdot 10^k + y \equiv 0 \pmod{x+y}↵
\ \iff\↵
x(10^k-1) \equiv 0 \pmod{x+y}.↵
$$↵
↵
Let $d=\gcd(x,y)$, $x=ad,\ y=bd$. Then $x+y = d(a+b)$.↵
The divisibility condition becomes:↵
↵
$$↵
d(a+b) \mid ad(10^k-1) \ \iff\ (a+b)\mid a(10^k-1).↵
$$↵
↵
Since $\gcd(a,a+b)=1$, we conclude:↵
↵
$$↵
\boxed{\,a+b \mid 10^k-1\,}.↵
$$↵
↵
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:↵
↵
$$↵
\boxed{\,y = dM - x,\quad d \mid x,\quad M \mid (10^k-1),\quad 10^{k-1}\le y < 10^k\,}.↵
$$↵
↵
The last inequality ensures that $y$ has exactly $k$ digits.↵
Equivalently:↵
↵
$$↵
\left\lceil \frac{x+10^{k-1}}{d}\right\rceil \le M \le \left\lfloor \frac{x+10^k-1}{d}\right\rfloor.↵
$$↵
↵
---↵
↵
## 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)↵
↵
```cpp↵
#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:↵
↵
$$↵
(x \cdot 10^k + y) \bmod (x+y) = ( (x \bmod (x+y)) \cdot (10^k \bmod (x+y)) + y ) \bmod (x+y).↵
$$↵
↵
Since $(x+y) < 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)↵
↵
```cpp↵
#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:↵
↵
$$↵
y = dM - x,\quad d \mid x,\quad M \mid (10^k-1).↵
$$↵
↵
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.
↵
*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 < 10^8$).↵
We want to find an integer $y$ ($1 \le y < 10^9$) such that↵
↵
$$↵
x\#y \equiv 0 \pmod{x+y}, ↵
\quad\text{where}\quad↵
x\#y = x \cdot 10^k + y,↵
$$↵
↵
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:↵
↵
$$↵
x \cdot 10^k + y \equiv 0 \pmod{x+y}↵
\ \iff\↵
x(10^k-1) \equiv 0 \pmod{x+y}.↵
$$↵
↵
Let $d=\gcd(x,y)$, $x=ad,\ y=bd$. Then $x+y = d(a+b)$.↵
The divisibility condition becomes:↵
↵
$$↵
d(a+b) \mid ad(10^k-1) \ \iff\ (a+b)\mid a(10^k-1).↵
$$↵
↵
Since $\gcd(a,a+b)=1$, we conclude:↵
↵
$$↵
\boxed{\,a+b \mid 10^k-1\,}.↵
$$↵
↵
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:↵
↵
$$↵
\boxed{\,y = dM - x,\quad d \mid x,\quad M \mid (10^k-1),\quad 10^{k-1}\le y < 10^k\,}.↵
$$↵
↵
The last inequality ensures that $y$ has exactly $k$ digits.↵
Equivalently:↵
↵
$$↵
\left\lceil \frac{x+10^{k-1}}{d}\right\rceil \le M \le \left\lfloor \frac{x+10^k-1}{d}\right\rfloor.↵
$$↵
↵
---↵
↵
## 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)↵
↵
```cpp↵
#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:↵
↵
$$↵
(x \cdot 10^k + y) \bmod (x+y) = ( (x \bmod (x+y)) \cdot (10^k \bmod (x+y)) + y ) \bmod (x+y).↵
$$↵
↵
Since $(x+y) < 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)↵
↵
```cpp↵
#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:↵
↵
$$↵
y = dM - x,\quad d \mid x,\quad M \mid (10^k-1).↵
$$↵
↵
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.
