AOJ NTL_1_B Power

備忘録

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_1_B&lang=jp

回答

import sys, os, math, bisect, itertools, collections, heapq, queue, copy, array

# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from decimal import Decimal
# from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
INF = float('inf')


def pow_mod(m, n, p=MOD):
    if n == 0: return 1
    if n == 1: return m % p
    if n % 2 == 1: return (m * pow_mod(m, n - 1, p)) % p
    ret = pow_mod(m, n // 2, p)
    return (ret * ret) % p


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    m, n = il()
    print(pow_mod(m, n, MOD))


if __name__ == '__main__':
    main()

考え方

螺旋本より、べき乗を行う問題。
最大で100を10^9回乗算する必要があるため、繰り返し二乗法を用いて高速化する。

【競プロ】繰り返し二乗法と再帰関数 | なかけんの数学ノート

---

ただし、Pythonのpowは繰り返し二乗法で実装されており、
十分に高速なので以下のコードでも正解となる。

MOD = 10 ** 9 + 7
x,y=map(int,input().split())
print(pow(x, y, MOD))