Codeforces Round 2140 Problem B

Problem summary: We are given an integer x < 10^8. We need to find a positive integer y < 10^9 such that the concatenation x#y (x followed by y) is divisible by (x + y).

Concatenation can be written as: x#y = x * 10^d + y

where d = number of digits in y.
We want:

x * 10^d + y = (x + y) * p

for some integer p.

Solving for y: y = x * (10^d — p) / (p — 1)

Let p - 1 = t.

y = x * ( ((10^d — 1)/t) — 1 )

Notice that 10^d - 1 is always like 999...9.

If we choose t to be numbers like 111..1 (all 1’s), the formula simplifies nicely.

• With t = 111..1, we get y = 8x.
• With t = 333..3, we get y = 2x.