言語:python 3.9.1

❓ Problem

白駿1629。乗算＃ジョウサン＃

📕 フィードバック

1.発展方向

対称性をよく観察し,正しければ再帰関数を用いた一方の値を再利用する.

2.感じる

分かれて治めるのは回帰だ.しかし、この場合、両側が分かれているのではなく、両側に耳を回します.対称だから!!対称の場合、両方に対してマルチ再帰関数を呼び出す必要がない類似の結果が生成されます.つまり繰り返しです.

🚩 Solution

1.方法

TRY 1

powを使います.2%になってタイムアウトしました

TRY 2

分割征服を利用してタイムアウトする.理由powを使用する場合と同じ時間複雑度

TRY 3

left_remain=right_remain*arightの残りを再取得すれば自然に取れるleft_remain(対称なので)

TRY 4

でも奇数の場合と偶数の場合では違います!
考えてみれば、奇数の場合は左がN/2+1、偶数の場合は左がN/2です.
そこで、left_remain偶数と奇数に分けるright_remain値(再帰的に調べた値)から導出

2.コード

import sys; read = sys.stdin.readline

A, B, C = tuple(map(int, read()[:-1].split(" ")))

def findRemain(a, b):
    # 종결조건
    if (b==1):
        return a%C
    else:
        right_remain = findRemain(a, b//2); left_remain = right_remain*a if b%2 == 1 else right_remain
        return (left_remain*right_remain)%C

print(findRemain(A%C, B))

3.結果

じかんふくごうどぶんせき

O(logB)