E - Last 9 Digits Editorial
by 
square1001
前提知識
この問題を解くためには、以下の 2 つの前提知識が必要です。
整数の剰余：\(a\) を \(b\) で割った余りは \(a \bmod b\) と表記します。
繰り返し二乗法：\(a^b \bmod m\) を計算量 \(O(\log b)\) で求めるアルゴリズムです。
また、この解説の証明を理解するためには、以下の 2 つの前提知識が必要です。
二項定理：\((a+b)^n = {}_n C_0 a^0 b^n + {}_n C_1 a^1 b^{n-1} + \dots + {}_n C_n a^n b^0\) が成り立ちます。
オイラーの定理：\(a\) と \(m\) が互いに素（最大公約数が \(1\)）のとき、\(a^{\varphi(m)} \bmod m = 1\) となります。ここで、\(\varphi(m)\) は \(1, 2, \dots, m-1\) のなかで \(m\) と互いに素なものの個数です。
いずれも プログラミングコンテストチャレンジブック第 2 版 などで紹介されている競技プログラミングの典型知識ですので、知らなかった方はこの機会にぜひ知っておきましょう。
答えはひとつだけ
競技プログラミングでは、入力例などのケースで「実験」を行うことで、解法の手がかりとなる性質をつかめる場合があります。
早速、入力例の \(X = 27\) のケースを考えます。まず、\(n=3\) のとき \(n^n \bmod 10^9 = 27\) となりますが、それ以外の \(n\) でもそうなるかもしれません。
そこで、実際に以下の Python プログラムを書いて確かめてみると、実行には数十分かかりますが、答えは \(n = 3, 1000000003, 2000000003, \dots\) と求まります（補足：プログラムを C++ で書くとより速く実行できます）。
for n in range(3*10**9):
if pow(n, n, 10**9) == 27:
print(n) # n^n を 10^9 で割った余りが 27 なら、n を出力
次に、\(X = 3\) のケースを考えます。\(n^n \bmod 10^9\) が \(3\) となるのは、\(n = 595998427, 1595998427, 2595998427, \dots\) のときです。この時点で、以下の予想が立ちます。
予想 \(X\) を \(2, 5\) の倍数でない整数とする。このとき、\(n^n \bmod 10^9 = X\) となるのは、\(n = a, 10^9+a, 2 \cdot10^9+a, \dots\) のとき（\(a\) は \(0\) 以上 \(10^9-1\) 以下の整数）である。
実はこの予想は正しいです。さらに、これは \(10^9\) の場合の問題だけでなく、同様の性質が \(10^k \ (k = 2, 3, 4, \dots)\) の場合の問題でも成り立ちます。これで解法への見通しが立ちやすくなりました。
小さな問題から大きな問題へ
競技プログラミングの問題を解くにあたって、小さいスケールの問題の答えを利用して、一段大きなスケールの問題の答えを求める、というテクニックがあります。これを使ってみましょう。
具体例として \(X = 3\) の場合を考えます。
- \(n^n \bmod 10^8 = 3\) となるのが、\(n = 95998427, 195998427, 295998427, \dots\) のときであることが、既に分かっているとします。
- \(n^n \bmod 10^9 = 3\) となるのは、予想 より \(n = a, 10^9+a, 2 \cdot 10^9+a, \dots\) のときですが、1. の結果より \(a\) は \(95998427, 195998427, \dots, 995998427\) の \(10\) 通りのいずれかとなります。
- \(10\) 通り全部確かめることで、\(a = 595998427\) と分かります。
このように、\(k \geq 3\) に対して、\(10^{k-1}\) の場合の問題の答えを利用して、\(10^k\) の場合の問題の答えを求めることができます。
アルゴリズム
問題の答えは以下のアルゴリズムで求められます。
- \(n^n \bmod 10^2 = X \bmod 10^2\) となる \(n\) を全探索で求める。この答えを \(a_2\) とする。
- \(k = 3, 4, \dots, 9\) の順に、以下を行う。
- \(n^n \bmod 10^k = X \bmod 10^k\) となる \(n\) を、\(n = a_{k-1}, 10^{k-1} + a_{k-1}, \dots, 9 \cdot 10^{k-1} + a_{k-1}\) の中から全探索で求める。この答えを \(a_k\) とする。
- 問題の答えは \(a_9\) である。
\(n^n \bmod 10^k\) は繰り返し二乗法を使って求めましょう。計算量は、桁数を \(L = 9\) として、\(O(L^2)\) となります。
予想の証明
最後に、この問題を解くのに使った 予想 の証明を行い、解説を完結させます。
まず、\(k \geq 2\) で \(X\) が \(2, 5\) の倍数でないとき、\(n^n \bmod 10^k = X\) となる \(1\) 以上 \(10^k-1\) 以下の \(2, 5\) の倍数でない整数 \(n\) が必ずひとつだけ存在する（★）ことを証明します。これは、アルゴリズムと同様に \(k = 2, 3, 4, \dots\) の順に考える戦略で証明できます。
まず \(k = 2\) の場合に（★）が成り立ちます。なぜなら、\(1^1, 3^3, 7^7, 9^9, 11^{11}, \dots, 99^{99}\) を \(100\) で割った余りの中に、\(1, 3, 7, 9, 11, \dots, 99\) が一度ずつ現れるからです。
次に \(k = 3\) の場合を考えます。\(n\) を \(1\) 以上 \(99\) 以下の \(2, 5\) の倍数でない整数とします。\(t = 0, 1, \dots, 9\) としたときの \((n + 100t)^{n + 100t}\) を考えます。二項定理からはじめて、以下のように式変形できます。
\[ \begin{aligned} (n+100t)^{n+100t} & = n^{n+100t} + (n+100t) \cdot n^{n+100t-1} \cdot 100t + \cdots + n^0 \cdot (100t)^{n+100t} \\ & \equiv n^{n+100t} + (n+100t) \cdot n^{n+100t-1} \cdot 100t \pmod{1000} \\ & \equiv n^{n+100t} + n \cdot n^{n+100t-1} \cdot 100t + 100t \cdot n^{n+100t-1} \cdot 100t \pmod{1000} \\ & \equiv n^{n+100t} + n \cdot n^{n+100t-1} \cdot 100t \pmod{1000} \\ & \equiv n^{n+100t} + n^{n+100t} \cdot 100t \pmod{1000} \\ & \equiv \left(n^n + n^n \cdot 100t \right) \cdot (n^{100})^t \pmod{1000} \end{aligned} \]
ここで \(n^{100} \bmod 1000 = 1\) が成り立ちます。なぜなら、オイラーの定理を使うと
- \(\varphi(8) = 4\) より \(n^4 \bmod 8 = 1\)、すなわち \(n^{100} \bmod 8 = 1\)
- \(\varphi(125) = 100\) より、\(n^{100} \bmod 125 = 1\)
が成り立つからです。したがって、上の式は以下のようになります。
\[(n + 100t)^{n + 100t} \equiv n^n + n^n \cdot 100t \pmod{1000}\]
ここで \(n^n\) は \(2, 5\) の倍数でないので、\(n^n, (n+100)^{n+100}, \dots, (n+900)^{n+900}\) を \(1000\) で割った余りに、\((n^n \bmod 100), (n^n \bmod 100) + 100, \dots, (n^n \bmod 100) + 900\) が一度ずつ現れます。よって、\(k = 2\) で（★）が成り立つことを使って、\(k = 3\) で（★）が成り立つことが分かります。
\(k = 4, 5, 6, \dots\) の場合も同様に証明できます。よって、どんな \(k \geq 2\) でも（★）が成り立ちます。
予想 を証明するためには、あとは「\(n\) が \(2\) の倍数か \(5\) の倍数のとき \(n^n \bmod 10^k = X\) の解にならないこと」「\(n = a\) が \(n^n \bmod 10^k = X\) の解であれば、\(n = a + 10^k\) も解である」ことを証明すれば十分です。前者は明らかで、後者については、先ほどの式変形の結果から、直ちに \((n+100t)^{n+100t} \equiv n^n \pmod{100}\) が分かり、同様に \((a+10^k)^{a+10^k} \equiv a^a \pmod{10^k}\) も分かります。
解答例
C++ での実装例は https://atcoder.jp/contests/arc172/submissions/50322918 です。
また、Python では以下のように実装できます。
# Python では a^b を m で割った余りを pow(a, b, m) で求められる
# 問題を解く関数
def solve(x):
# n の下 2 桁を求める
for i in range(1, 100):
if pow(i, i, 100) == x % 100:
n = i
# n の下から 3, 4, ..., 9 桁目を順番に求める
for i in range(3, 10):
m = 10 ** (i-1)
for j in range(10):
if pow(n+m*j, n+m*j, m*10) == x % (m*10):
n += m * j
break
return n
# メインの部分
q = int(input())
for _ in range(q):
x = int(input())
print(solve(x))
posted:
last update: