回答編集履歴

1

半角※を✖️に。

2023/01/18 15:39

投稿

matukeso
matukeso

スコア1588

test CHANGED
@@ -1,8 +1,8 @@
1
1
  calc(N) = mod10(2^N)なので
2
- Nが奇数のとき、N=2k+1とおくと calc(N) = mod10(2*(2^2k))=mod10(2*mod10(2^k)^2)=mod10(2*calc(k)^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*2)なので、calc(2)を呼んで、calc(2)=mod10(calc(1)^2)なので、calc(1)を呼んで、calc(1)=mod10(2*calc(0)^2)なので、calc(0)を呼ぶ。
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*1^2)=2, calc(2) = mod10(2^2)=4, calc(5)=mod10(2*4^2)=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