繰り返し二乗法

・x**yを使わないといけないのに、yの制約が「0≦y≦10**9」とかのとき。

①"aのn乗"の計算

def reppow(a,n):
  if n == 0:
    return 1
  if n == 1:
    return a
  if n%2 == 1:
    ret = reppow(a,n-1)*a
    return ret
  ret = reppow(a,n//2)
  ret = ret*ret
  return ret

このままgoogle colabなどで

reppow(3,100000)

で実行（して、結果を表示）しようとすると

ValueError: Exceeds the limit (4300) for integer string conversion; use sys.set_int_max_str_digits() to increase the limit

となってしまう。

import sys
sys.set_int_max_str_digits(10**6)

これで解決。
ただし、この桁数をそのまま競プロで使うことはなさそうなので、なにかしらのmodを取るような設問にはなりそう。
逆に、4300桁で収まるくらいなら繰り返し二乗法でなくても良い程度の計算量に収まりそう。

②"aのn乗をpで割ったあまり"の計算

import sys
sys.setrecursionlimit(10**9)

def modpow(a,n,p):
  if n == 0:
    return 1
  if n == 1:
    return a%p
  if n%2 == 1:
    ret = modpow(a,n-1,p)*a
    return ret%p
  ret = modpow(a,n//2,p)
  ret = ret*ret
  return ret%p

pypyなら、

import pypyjit
pypyjit.set_param('max_unroll_recursion=-1')

も忘れずに追加しておく。