30歳で競プロに目覚めた霊長類のブログ

チンパンジーと一般人のあいだ

ARC111-A Simple Math 2

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

問題リンク
A - Simple Math 2

問題概要

 \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 で一度考えてみることにします。

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

次に、  y \mod M の意味を考えます。
これは読んでそのまま、 yM で割ったあまりです。
 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_0M進数における下から1桁目、k_1M進数における下から2桁目... です。
 x = pM^2 + qM + b と係数を比較すると、
k_0 = b, k_1 = q となります。
したがって、求めたい数値はqなので、 xM 進数で表したときの下から 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^NM^2 で割った余り」を高速に求めてくれます。2
上述の式で、 10^N = pM^2 + qM + b と表せるところの、
 qM + b が求まります。
これを // MM で切り捨て除算することで、求める答えである q が得られます。

おわり

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


  1. 私はこの言い換えすらコンテスト中にできませんでした…

  2. 愚直に求めるとTLEやMLEを起こすのですが、第3引数にMODの値を入れることで高速にMODをとりながらの累乗を求めてくれます。このような機能のない言語では繰り返し2乗法という手段を使うと思うのですがそのようなライブラリがないと辛いですよね。。