https://www.acmicpc.net/problem/1629
풀이
간단하지만 수의 크기때문에 생각의 시간이 필요했던 문제.
(A * B) % C = (A%C * B%C) %C
위처럼 생각하여 C로 나누어 주어 숫자를 줄여 풀이가 가능하다.
Code ( C++ )
#include <iostream>
using namespace std;
long long pow(long long A, long long B, long long C)
{
if (B == 0)
return 1;
if (B == 1)
return A % C;
long long result = pow(A, B / 2, C);
result = result * result % C;
if (B % 2 == 0)
return result;
return result * A % C;
}
int main()
{
long long A, B, C;
cin >> A >> B >> C;
cout << pow(A, B, C);
}
'💻 OnlineJudge > Baekjoon' 카테고리의 다른 글
[백준 / BOJ] C++ 1918 후위 표기식 (0) | 2022.11.24 |
---|---|
[백준 / BOJ] C++ 1753 최단경로 (0) | 2022.11.16 |
[백준 / BOJ] C++ 1504 특정한 최단 경로 (0) | 2022.11.10 |
[백준 / BOJ] C++ 1238 파티 (0) | 2022.11.10 |
[백준 / BOJ] C++ 1167 트리의 지름 (0) | 2022.11.03 |