整数 Nが与えられたときの２^Nを10で割った余りを計算しなさい

Question

前提

アルゴ式で競プロの勉強した際に出てきたプログラムが理解できない

理解できない点

・4行目のreturn 1がどのような処理を行っているのか
・7～11行目がどのような処理を行っているのか

発生している問題

「整数 Nが与えられたときの２^Nを10で割った余りを計算しなさい」という問題のサンプルプログラムが理解できない

該当のソースコード

def calc(N):
    # 終端条件
    if N == 0:
        return 1

    # たとえば 2^10 = 2^5 * 2^5、2^11 = (2^5 * 2^5) * 2
    half = calc(N // 2)
    res = half * half
    if N % 2 == 1:
        res *= 2
    return res % 10

N = int(input())
print(calc(N))

試したこと

・「return1 意味」、「python 戻り値」などと検索する
・再帰関数について調べる

Answer 1

前半部分は累乗計算を再帰で記述していますね。
2 ^ ( N / 2)を計算し、これを自乗しています。なお、Nが奇数の場合はさらに2をかけます。
終了条件として、Nがゼロならば1を返すことと定義しています。

この方法であれば、Nの値に対する時間計算量がO(logN)となります。N回乗算する場合はO(N)なので、より小さいオーダになります。

Answer 2

簡単に、Nが2の整数乗（2,4,8,16,32,64,...）の場合を考えてみましょう。

たとえばN=8つまり「２^8乗を10で割った余り」を求めるとします。
８= 4 + 4 なので
「2^8乗を10で割った余り」は

• （2^4乗を10で割った余り　×　2^4乗を10で割った余り）を10で割った余り

と分解できます。

同様に、「2^4乗を10で割った余り」は 4=2+2 なので

• （2^2乗を10で割った余り　×　2^2乗を10で割った余り）を10で割った余り

で計算できます。
このように分解していくと最後に

• （2^0乗を10で割った余り　×　2^0乗を10で割った余り）を10で割った余り
• ＝（1 × １）を10で割った余り
• ＝ １

となります。
これが

    # 終端条件
    if N == 0:
        return 1

の部分です。

上の例を一般化して、プログラムでは
与えられた数をどんどん 2 で割っていく　（ half = calc(N // 2)　）
→ その数を10で割った余り [ calc(N // 2)] を求めて、2乗する。（res=half*half）
→ res を10で割った余りを求めて返す（ return res % 10）

という手順を踏んでいます。

---

ではNが奇数（奇数乗）の場合はどう計算すればよいのでしょうか。

たとえば N=7のとき（2^7乗を10で割った余り）の計算を考えてみましょう

このときは
7＝3＋3＋1なので

• （2^3乗を10で割った余り　×　2^3乗を10で割った余り　×　2^1乗 を10で割った余り）を10で割った余り

を求めればいいわけですね。

3つ目の「2^1乗 を10で割った余り」はすなわち 2 なので

• （2^3乗を10で割った余り　×　2^3乗を10で割った余り　× ２）を10で割った余り

を求めることになります。

この後半の「× ２」が

    if N % 2 == 1: res *= 2

の部分の意味です。

Answer 3

calc(N) = mod10(2^N)なので
Nが奇数のとき、N=2k+1とおくと calc(N) = mod10(2✖️(2^2k)) = mod10(2✖️mod10(2^k)^2) = mod10(2✖️calc(k)^2)
Nが偶数のとき、N=2kとおくとcalc(N) = mod10(2^2k) = mod10(mod10(2^k)^2) = mod10(calc(k)^2)
それぞれ分解できる。つまり、calc(k)が解っていれば、calc(2k)かcalc(2k+1)の計算を返せる。 これが7-11行目の処理。おなじくcalc(k)はcalc(2j)かcalc(2j+1)をつかって計算できるので、どんどんNを小さくしてcalcを呼び出していき、最後はcalc(0)にたどり着く。この値はmod10(2^0)=1。

たとえば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)を呼ぶ。
calc(0)で4行目のreturnにたどり着くと、そこから呼び出し（途中の計算）が戻っていく。
calc(0)=1, calc(1)=mod10(2✖️1^2)=2, calc(2) = mod10(2^2)=4, calc(5)=mod10(2✖️4^2)=2

Comments

[bamboooo]

とてもわかりやすい解説で納得できました。ありがとうございます。
解説を読んで湧いてきた質問なのですが、9,10行目のNが奇数の際にresを2倍するという処理はなぜ行うのでしょうか。

[matukeso]

Nが奇数のとき、N=2k+1とおくと、の文が理解できないということですか？
2^(2k+1)=2✖️((2^k)^2)で、resは(2^k)^2を意味しているからですが。

[bamboooo]

ソースコードの9，10行目のif N % 2 == 1: res *= 2の部分が理解できないという意味です。
質問の仕方がわかりにくくてすみません。