# yukicoder No.1842

「$A$ の末尾に数字の 0 を $C$ 個つけた整数」を $B$ で割ったときの商の 1 の位を求める問題である、と読み替える。この問題は、こう読み替えると正解に近づいていることを認識するのが一番難しく、ここを突破すればあとは ARC 111 A - Simple Math 2 https://atcoder.jp/contests/arc111/tasks/arc111_a のように考えることができる。ちなみに ARC111A はコレはコレで難しいと話題になった。
「$A$ の末尾に数字の 0 を $C$ 個つけた整数」は $A \times 10^{C}$ であり、これを $A'$ としておく。

除法の原理というのがある。何てことはなく、当たり前のことだと思うだろう。

| 除法の原理 |
| ----------- |
| 整数 $a$ と正の整数 $b$ に対して、次を満たす整数 $q, r$ がただ一組存在する。<br> $a = qb + r \quad (0 \le r \le b-1)$ <br> 整数 $q, r$ をそれぞれ $a$ を $b$ で割ったときの商、余りという。 |

$a$ から $b$ をどんどん引いて（$a$ が負なら $b$ をどんどん足して）いけば、いつかは $0$ 以上 $b$ 未満になり、そのときの操作回数が $q$ の絶対値になるわけで、$q, r$ が存在することは分かった。

仮に $q, r$ の他に $q_{0}, r_{0}$ も答えであったとすると、$a = qb + r = q_{0}b + r_{0}$ なので $b(q - q_{0}) = r_{0} - r$.
つまり $r_{0} - r$ は $b$ の倍数である。$r_{0}$ は $r$ と同様 $0 \le r_{0} \le b-1$ なので、$b$ の倍数であることが判明した $r_{0} - r$ はゼロにしかなりえない。$b$ がゼロでないので、$q - q_{0}$ がゼロになる。これは $q = q_{0}$ で $r = r_{0}$ でもあるということで、一意だということも分かった。■

読み替えた問題に除法の原理を使うと
$A' = qB + r \quad (0 \le r \le B-1)$
となるような整数 $q, r$ を持ってくることができて、答えは整数 $q$ の 1 の位（10 で割った余り）である。[^1]
[^1]: なお、今回のケースでは $q$ が負になることを考えなくていい。

つまり、もう一度除法の原理を使って
$q = 10q' + D \quad (0 \le D \le 9)$
としたときの $D$ が答えになる。

よって、
$\begin{eqnarray}
A' &=& qB + r \\
&=& (10q' + D)B + r \\
&=& 10Bq' + (BD + r)
\end{eqnarray}$

最後の部分は $A'$ を $10B$ で割った余りが $BD + r$ だと見ることができる。余りとしての条件を満たしていることを確認しておくと、
$\begin{align}
0 &\le D \le 9 \\
0 &\le BD \le 9B \\
0 &\le BD + r \le 10B-1
\end{align}$
であり、確かに範囲として適切である。
求めたいのは $D$ なので、$BD + r$ を $B$ で割った商が答え。$r$ の範囲は先に考えたとおり $B$ で割った余りとしてふさわしい。

Python なら $A' = A \times 10^{C}$ を $10B$ で割った余りは

A * pow(10, C, 10*B) % (10*B)

と書けるだろう。これを $B$ で割った商が答えなので

A * pow(10, C, 10*B) % (10*B) // B

が求めるものとなる。

参考：受験の月 https://examist.jp/mathematics/integer/jyohou/