Concat Two Coprimes

解説

$N$ が $2$ の倍数のとき、$b$ が必ず $2$ の倍数となってしまい $N$ と $b$ が必ず公約数 $2$ を持ちます。
同様に $N$ が $5$ の倍数のときも $N$ と $b$ が必ず公約数 $5$ を持ちます。

よって、 $N$ が $2$ の倍数または $5$ の倍数のときは、条件を満たす $X$ は存在しません。
逆に、それ以外の場合は $X$ が存在します。以下、その事実を証明します。

---

証明

$N$ と $1$ は必ず互いに素なので、 $b = 1$ と固定すると $f(a, 1) = 10a + 1$ が解の候補となります。
ここで、仮定より $N$ は $10$ と互いに素であることが言えます。

よって $10a' \equiv 1 ~ (\mathrm{mod} ~ N)$ なる $a'$ は必ず存在し、$a = N - a'$ と置くと $10(N - a) \equiv 1 \Longleftrightarrow 10a \equiv -1$ なる $a$ も存在します。

したがって $f(a, 1) \equiv -1 + 1 \equiv 0 ~ (\mathrm{mod} ~ N)$ が存在し、これは $N$ の倍数です。

---

さて、ここで得られた $X$ は $10N$ 以下です。 $a \lt N$ としても上記の証明が成立し、$f(a, 1) \lt 10N + 1$ が成り立つためです。

よって、解が存在する場合は以下のアルゴリズムで十分高速に解くことができます。

• $N$ の倍数 $x = N, 2N, 3N, \cdots$ を昇順に判定していき、$x$ が条件を満たすならばそれを答えとする。

判定時、 $b$ が leading-zero であるときは $f$ の定義を満たしていないため条件を満たさないことに注意してください。

判定部分が $O(\log N)$ 、探索範囲が $O(1)$ 個であるため、全体の計算量 $O(T \log N)$ で解くことができます。