모듈러 연산의 성질
모듈러 연산은 다음과 같은 성질을 가지고 있다. 분배법칙이 성립하기 때문에, 미리 모듈러 연산을 해도 결과에 영향을 미치지 않는다. 이는 결과 값이 모듈러 연산에 대한 값일 때, 계산중에 미리 모듈로 연산을 해도 된다.
제곱수의 DP
이 문제에서 가장 곤란한 점은 A를 B번 곱해야하는데, B의 수가 상당히 커질 수 있다는 점이다. A에는 모듈러 연산을 미리 취하면 된다지만, B는 해결할 방법이 없다.
이를 해결하기 위해서 재귀함수로, 2N 제곱수의 연산을 계산한다.
예를 들면 2^4를 계산할 때, 2^2를 계산하고 이를 제곱하는 방식이다. 이렇게 하면, O(longN)의 시간 복잡도를 달성할 수 있다.
Source Code
#include <iostream>
#include <algorithm>
typedef long long ll;
using namespace std;
int A, B, C;
int DP(ll a, ll b){
if(b == 1) return a % C;
ll ret = DP(a, b/2) ;
ret = (ret * ret) % C; // 이미 계산한 것을 사용해 주자!
if(b % 2 != 0) ret = (ret * a) % C;
return ret;
}
int main(){
cin >> A >> B >> C;
cout << DP(A,B) << endl;
return 0;
}
// (a*b) % c == (a%c) * (b%c)
Hi~