ARC111 A - Simple Math 2 解説

問題

https://atcoder.jp/contests/arc111/tasks/arc111_a

解法

開く

$10N10^N$ を $M2M^2$ で割ったあまりを $MM$ で割って切り捨てる

解説

$MM$ 進法で考えます。
すると、 $⌊XM⌋\lfloor \frac X M \rfloor$ は、 $XX$ の下 $11$ 桁を取り除いたものになります。
これを $MM$ で割ったあまりは、 $⌊XM⌋\lfloor \frac X M \rfloor$ の下 $11$ 桁、つまり $XX$ の下から $22$ 桁目になります。
これを求めるには、 $XX$ を $M2M^2$ で割ったあまりを $MM$ で割って切り捨てればよいです。

例として、 $M=8M = 8$ 、 $N=3N = 3$ のときを考えます。
$10N=100010^N = 1000$ になりますが、これは $MM$ 進数 では $175081750_8$ です。（ $8_8$ は $88$ 進数の意味です）
$175081750_8$ の下から $22$ 桁目は $55$ であり、これが答えです。

コード

N, M = gets.split.map(&:to_i)
puts 10.pow(N, M**2) / M