ARC111-A Simple Math 2 - ごりちゃんがゆく

Simple (笑) とは...
コンテスト中に解けなかったので、どうやったら自然に解けるようになるか整理してみます

問題概要

$\lfloor \frac{10^N}{M} \rfloor \mod M$ を求めよ
( $\lfloor x \rfloor$ は $x$ の整数部分)
$1 \le N \le 10^{18}(クソデカ), 1 \le M \le 10^4$

M=10で題意を理解してみる

まずは題意を感覚で理解しようとしてみます
maspy さんのおっしゃるように、 $M=10$ で一度考えてみることにします。

mod Mの基礎的なことが非自明に感じる方は、mod 10 の場合を考えるのも良いかもしれません。例えば「ab mod M は a mod M, b mod M から分かる」とかM=10だと知っていますよね。

昨日のAも
「(a^b//10) mod 10 を求めよ」であれば、
「a^b mod 100 があればよい」とすぐに分かる方、増えませんかね。
— maspy (@maspy_stars) January 10, 2021

$10^N$ の部分はとりあえず適当に $12345$ とかにしといて、 $M=10$ を代入します
$\lfloor \frac{12345}{10} \rfloor \mod 10$
これの、
$\lfloor \frac{12345}{10} \rfloor$ の部分は、
$1234.5$ の整数部なので $1234$ となります。
したがって
$1234 \mod 10$ となり、 $4$ が得られます。

実はこの問題の題意は、 $10^N$ (クソデカ数) を $M$ 進数で表したときの下から $2$ 桁目を出力せよ と同じなのです。

本当に？

$\lfloor \frac{x}{M} \rfloor$ の意味を改めて考えてみます。
これは、 $x$ を $M$ で割った商です¹
$x ÷ M = a あまり b$ と表されるとき、
$x = aM + b$ となります。商が $a$ 、あまりが $b$ です
整数部分を取る操作は、あまりを無視した商の部分ですので、
$\lfloor x ÷ M \rfloor = \lfloor \frac{x}{M} \rfloor = a$ です。

次に、 $y \mod M$ の意味を考えます。
これは読んでそのまま、 $y$ を $M$ で割ったあまりです。
$y ÷ M = p あまり q$ と表されるとき、
$y = pM + q$ となります。これの、 $q$ の部分が $y \mod M$ です。

さて、求めたいものは $\lfloor \frac{x}{M} \rfloor \mod M$ でした。
$y = \lfloor \frac{x}{M} \rfloor$ として、まず $\mod M$ の式に当てはめます
$y = \lfloor \frac{x}{M} \rfloor = pM + q$
(↑これの $q$ の部分が求めたい答えです)
次に、 $x = aM + b$ 、 $\lfloor \frac{x}{M} \rfloor = a$ を使います。
$a = pM + q$ となるので、
$x = (pM + q)M + b = pM^2 + qM + b$
となります。

ここで、 $M$ 進数とは、 $x$ をこのように分解して表した表現だと言えます。
$x = k_0M^0 + k_1M^1 + k_2M^2 + k_3M^3 + ...$
$k_0$ が $M$ 進数における下から $1$ 桁目、 $k_1$ が $M$ 進数における下から $2$ 桁目... です。
$x = pM^2 + qM + b$ と係数を比較すると、
$k_0 = b, k_1 = q$ となります。
したがって、求めたい数値は $q$ なので、 $x$ を $M$ 進数で表したときの下から $2$ 桁目を出力せよ と言い換えることができました！
なお、残りの部分は $M^2$ で括れるので $k_2M^2 + k_3M^3 + ... = pM^2$ として良いです (が本問では無視して良いです)

実装

Pythonが本領発揮できるところでした
以下でACしました！

N,M = map(int,input().split())
ans = pow(10,N,M*M) // M
print(ans)

ここで、 pow(10,N,M*M) は、Pythonでは「 $10^N$ を $M^2$ で割った余り」を高速に求めてくれます。²
上述の式で、 $10^N = pM^2 + qM + b$ と表せるところの、
$qM + b$ が求まります。
これを // M で $M$ で切り捨て除算することで、求める答えである $q$ が得られます。

おわり

simple (笑) とは... という感じだったけど、分かってしまえばなるほど simpleかもです
しかし 300点緑difficultyとは納得しがたい...
いずれにしても、数式を見て一目で分かるぐらいには慣れていきたい...！

私はこの言い換えすらコンテスト中にできませんでした…↩
愚直に求めるとTLEやMLEを起こすのですが、第3引数にMODの値を入れることで高速にMODをとりながらの累乗を求めてくれます。このような機能のない言語では繰り返し2乗法という手段を使うと思うのですがそのようなライブラリがないと辛いですよね。。↩