C1: Doubling Powers

解説

量子競技プログラミングコンテストでどうして古典計算をさせるのかと思った方も多いかもしれません。 ショアのアルゴリズムでは古典計算を時間計算量を無視して雑に行ってしまうと、量子計算部分を頑張った意味が無くなってしまいます。 よって、古典計算の知識は多少必要になります。

問題文の通りそのまま計算すると 時間制限超過 (TLE) や メモリ使用量超過 (MLE) になりますが、2乗を繰り返す事で掛け算の回数を減らすことができます。 また、計算中は $L$ を超えたら常に mod を取ることで、桁数が上がり続けるのを抑えることができます。

解答例

解答例は以下の通りです。

def solve(n: int, a: int, L: int) -> list:
    result = [a]
    for _ in range(n - 1):
        result.append(result[-1] ** 2 % L)
 
    return result