BOJ13171. A

작성일

https://www.acmicpc.net/problem/13171

  • 다른 문제에서 Snippet으로 이용하는 중요한 문제
  • 특히나 점화식 행렬로 바꿔서, 피보나치 같은거 가속할때 쓴다.
  • C++로 짜면 for문으로 한줄로 바꿀수 있는게 매력적이다.
  • 또다른 중요한 포인트중 하나는 MOD가 소수이기 때문에 지수부도 MOD-1로 나머지 계산 할 수 있다는 점이다.
    • 확장 유클리드랑 페르마의 소정리를 이용해야 한다. 여길 참고.
1
2
3
4
5
6
7
8
9
10
11
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007LL;
long long base, p, ans = 1, cur;
int main() {
  cin >> base >> p;
  p %= MOD - 1;
  for(cur = base%MOD; p > 0; p /= 2, cur = cur*cur%MOD)
    ans = p&1 ? ans*cur%MOD : ans;
  cout << ans;
}
  • 파이썬으로도 풀었다. 개인적으로 _를 포함한 숫자표기는 진짜 짱인듯.
1
2
3
4
5
6
7
8
9
10
11
12
13
MOD = 1_000_000_007
def power(base, p):
    ans = 1
    cur = base
    while p > 0:
        ans = (cur * ans) % MOD if (p & 1) else ans
        cur = (cur * cur) % MOD
        p //= 2
    return ans

base = int(input()) % MOD
p = int(input())
print(power(base, p))