こんにちは。和から数学講師の栗原です。

最近競技プログラミングにハマっており、AtCoderというサイトで毎週のようにコンテストに参加しています。競技プログラミングでは数学色の強い問題が出題されることも多く、身につけた知識を実践形式でアウトプットできるとても良い場だと思います。

今回はそんな競技プログラミングの魅力の一端をお伝えすべく、数学色の強い問題を 1 問取り上げ、その解説をしてみたいと思います。ではさっそく問題を見ていきましょう。

1.問題

出典：AtCoder Regular Contest 113 B – A^B^C

以下が問題文です（少し表現を変えています。）

　
この問題を解くプログラムを書くことが目標となります。

$A^{B^C}$はとんでもなく大きな数になり得るので、いくらコンピュータとはいえ「単に計算するだけ」とはいきません。どのように工夫すれば 2 秒以内に答えを求めることができるでしょうか。

それでは解説に移ります。なお、解説中に記載してあるPtyhonのコードは Google Colaboratory や Jupyter Notebook上で実行してみることができます。

2.$A=23, B=43, C=1$のとき

いきなり$A^{B^C}$を考えるのは難しいので、まずは$C=1$のケースを考えてみましょう。さらに考えやすくするため、 $A=23,B=43$の場合を例にして考えていきます。

　　
 a = 23
 result = []
 for b in range(12):
   result += [a**b]
 result

 ---出力----
 [1,
  23,
  529,
  12167,
  279841,
  6436343,
  148035889,
  3404825447,
  78310985281,
  1801152661463,
  41426511213649,
  952809757913927]
　　

　
こういう観察が手軽にできるのが Python の良いところですね。計算結果の$1$の位の数は$1, 3, 9, 7, 1, 3, 9, 7, 1, 3, 9, 7, \ldots$ となっています。よく見ると4つずつの繰り返しになっていることに気づきます。

このことを納得するには、筆算で計算するときの手順をイメージしてみると良いでしょう。例えば$529$の次が$12167$なのは$529\times 23=12167$だからですが、これを筆算で計算するとき、$9×3=27$から計算し始めるはずです。その後がどうであれ、計算結果の$1$の位が$7$になることはこの時点で確定しています。

結局$1$の位だけを計算していくと、

• ・$1×3=3$
• ・$3×3=9$
• ・$9×3=(2)7$
• ・$7×3=(2)1$

となり、4 回で元の$1$に戻ってきます。以降は同じことの繰り返しになります。

さて、4つずつの繰り返しになるとわかったので、$B$から遡って考えると、
$${23}^{43},{23}^{39},{23}^{35},{23}^{31},\ldots$$
の$1$の位は全て同じだということになります。
$$43\div 4=10 \mbox{あまり} 3$$
なので、$43$からは$4$を$10$回引くことができ最後に$3$余ります。したがって、${23}^{43}$の$1$の位は${23}^3$の$1$の位と同じ$7$であることがわかりました。

このくらいなら単純計算もできるため、念のため確認しておきましょう。

　　
 23**43
 ---出力----
 35834136918934220777541995677272642015423987712183913488967
　　

　
確かに$1$の位は$7$で合っていますね。

3.$A=23, B=43, C=63$のとき

次は$C=63$にしてみましょう。

もはや${23}^{{43}^{63}}$はコンピュータの力を持ってしても簡単に計算できる大きさではありませんが、2節での観察で見た通り、${43}^{63}$を$4$で割った余りさえわかれば答えは求まります。

ところで2節で求めた${23}^{43}$の$1$の位は、${23}^{43}$を$10$で割った余りとも言い換えられます。こう言い換えてみると、${43}^{63}$を$4$で割った余りも先と同じ方法で求められそうな気がします。

${43}^0$から${43}^{11}$までを$4$で割った余りを観察してみます。

　　
 b = 43
 result = []
 for c in range(12):
   result += [(b**c) % 4]
 result
 ---出力----
 [1, 3, 1, 3, 1, 3, 1, 3, 1, 3, 1, 3]
　　

　
期待通り、$4$で割った余りは$1, 3, 1, 3, \ldots$ と2つずつの繰り返しになっていますね。

$$63\div 2=31\mbox{あまり}1$$
ですから、$63$からは$2$を$31$回引くことができ$1$余ります。これに倣って$C$から遡って考えると
$${43}^{63},{43}^{61},{43}^{59},{43}^{57},\ldots,{43}^1$$
を$4$で割った余りは全て同じです。したがって、${43}^{63}$を$4$で割った余りは${43}^1$を$4$で割った余りと同じ$3$であることがわかりました。

${43}^{63}$を$4$で割った余りが$3$なので、2節と同様に考えることで、${23}^{{43}^{63}}$の$1$の位は${23}^3$の$1$の位と同じであることがわかります。2 節で計算したようにこれは$7$でしたから、求める答えが$7$だとわかりました。

4.一般の$A,B,C$の場合

ではいよいよ一般の$A,B,C$について考えていきましょう。

3節での観察より、$A$の累乗の$1$の位（$10$で割った余り）と、$B$の累乗を$4$で割った余りに注目すれば良いはずです。

まずは$A$の累乗について一括で確認してみましょう。縦方向に$A$ 、横方向に何乗したか（ $0$～$11$ ）を並べます。

　　
 result = []
 for a in range(10):
   result += [[]]
   for b in range(12):
     result[-1] += [(a**b) % 10]
 result
 ---出力----
 [[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
  [1, 2, 4, 8, 6, 2, 4, 8, 6, 2, 4, 8],
  [1, 3, 9, 7, 1, 3, 9, 7, 1, 3, 9, 7],
  [1, 4, 6, 4, 6, 4, 6, 4, 6, 4, 6, 4],
  [1, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5],
  [1, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6],
  [1, 7, 9, 3, 1, 7, 9, 3, 1, 7, 9, 3],
  [1, 8, 4, 2, 6, 8, 4, 2, 6, 8, 4, 2],
  [1, 9, 1, 9, 1, 9, 1, 9, 1, 9, 1, 9]]
　　

　
どの行を見ても、2列目以降は1つずつ、2つずつ、または4つずつの繰り返しになっています。面倒な場合分けを防ぐため、いずれも4つずつの繰り返しになっているとみなすことにしましょう。

次は$B$の累乗について一括で確認してみましょう。縦方向に$B$、横方向に何乗したか（ $0$～$11$ ）を並べます。

　　
 result = []
 for b in range(4):
   result += [[]]
   for c in range(12):
     result[-1] += [(b**c) % 4]
 result
 ---出力----
 [[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
  [1, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [1, 3, 1, 3, 1, 3, 1, 3, 1, 3, 1, 3]]
　　

　
どの行を見ても、3列目以降は1つずつまたは2つずつの繰り返しになっています。こちらも面倒な場合分けを防ぐため、いずれも2つずつの繰り返しになっているとみなすことにしましょう。

後は 3節とほとんど同じですので、以下に解法としてまとめましょう。

5.解法

解法をまとめます。

$C\geq 2$のとき、
$$C\div 2=Q_C\mbox{あまり}R_C(0\leq R_C <2)$$ だとすると、 $$B^C,B^{C−2},B^{C−4},\ldots,B^{R_C+2}$$ を$4$で割った余りは同じです（ $B^{R_C}$を$4$で割った余りは異なる可能性があるので注意） よって $C$を$R_C+2$に置き換えてしまうことにします。これによって問題の答えが変わってしまう心配はありません。 $X=B^C$とおきます。 $X\geq 4$ のとき、 $$X\div 4=Q_X\mbox{あまり}R_X(0\leq R_X <4)$$ だとすると、 $$A^X,A^{X−4},A^{X−8},…,A^{R_X+4}$$ の$1$の位は同じです。（ $A^{R_X}$の$1$の位は異なる可能性があるので注意） よって$X$を$R_X+4$に置き換えてしまうことにします。これによって問題の答えが変わってしまう心配はありません。 以上の置き換えを行った上で$A^X$を計算すれば、その$1$の位が答えとなります。

6.実装例

以下 Python3での実装例です。

　　
 a, b, c = map(int, input().split())
 if c >= 2:
   c = c % 2 + 2
 x = b ** c
 if x >= 4:
   x = x % 4 + 4
 print((a ** x) % 10)
　　

7.まとめ

いかがでしたでしょうか。

具体例を作成、観察し、そこから規則性を見抜き、その理由を考える。それが一般化できるなら解法に繋げ、それを実現するプログラムを作る。
なんだかちょっとした研究のようですね。

競技プログラミングに興味をお持ちになった方は是非とも挑戦してみてください。ここまで読んでいただいてありがとうございました。

<文/栗原>