[BOJ 1629, 쉬움] 곱셈 (C++)

개인적인 난이도

쉬움

 

알면 1분만에 풀고 모르면 그냥 틀린다

매우 중요한 개념이 2 가지 들어있다. 정수론(모듈러 산술) & 분할정복(log N)

몰라서 2번 틀렸다
처음엔 정수론 몰라서 오버플로우로 틀리고 두번째엔 분할정복 몰라서 시간초과로 틀림

---

성공한 풀이)

 

핵심 1) 모듈러연산은 신기하게 덧셈 뺄셈 곱셈 분배법칙이 가능하다. 

핵심 2) 거듭제곱 계산(pow) 는 분할정복을 이용해 계산하면 log N 안에 끝남

 

성공한 코드

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
#define ll long long
using namespace std;
int main(void) {
	fastio;
	ll A,B,C;cin>>A>>B>>C;
	A%=C;
	ll ans = 1;
	while (B)
	{
		if(B%2==1){
			ans*=A;
			ans%=C;
		}
		B=B>>1;
		A*=A;A%=C;
	}
	cout<<ans%C;
	return 0;
}