回答編集履歴
1
半角※を✖️に。
test
CHANGED
|
@@ -1,8 +1,8 @@
|
|
|
1
1
|
calc(N) = mod10(2^N)なので
|
|
2
|
-
Nが奇数のとき、N=2k+1とおくと calc(N) = mod10(2
|
|
2
|
+
Nが奇数のとき、N=2k+1とおくと calc(N) = mod10(2✖️(2^2k)) = mod10(2✖️mod10(2^k)^2) = mod10(2✖️calc(k)^2)
|
|
3
|
-
Nが偶数のとき、N=2kとおくとcalc(N)=mod10(2^2k)=mod10(mod10(2^k)^2)=mod10(calc(k)^2)
|
|
3
|
+
Nが偶数のとき、N=2kとおくとcalc(N) = mod10(2^2k) = mod10(mod10(2^k)^2) = mod10(calc(k)^2)
|
|
4
4
|
それぞれ分解できる。つまり、calc(k)が解っていれば、calc(2k)かcalc(2k+1)の計算を返せる。 これが7-11行目の処理。おなじくcalc(k)はcalc(2j)かcalc(2j+1)をつかって計算できるので、どんどんNを小さくしてcalcを呼び出していき、最後はcalc(0)にたどり着く。この値はmod10(2^0)=1。
|
|
5
5
|
|
|
6
|
-
たとえばcalc(5)なら、mod10(calc(2)^2
|
|
6
|
+
たとえばcalc(5)なら、mod10(2✖️calc(2)^2)なので、calc(2)を呼んで、calc(2)＝mod10(calc(1)^2)なので、calc(1)を呼んで、calc(1)=mod10(2✖️calc(0)^2)なので、calc(0)を呼ぶ。
|
|
7
7
|
calc(0)で4行目のreturnにたどり着くと、そこから呼び出し（途中の計算）が戻っていく。
|
|
8
|
-
calc(0)=1, calc(1)=mod10(2
|
|
8
|
+
calc(0)=1, calc(1)=mod10(2✖️1^2)=2, calc(2) = mod10(2^2)=4, calc(5)=mod10(2✖️4^2)=2
|