백준 1629번 : 곱셈

문제 접근

---

처음에는 모듈러 연산 문제인 줄 알고 단순하게 구현했다. 그런데 2147483646 2147483646 2147483647 넣었을 때 시간이 굉장히 오래 걸렸다. 그래서 생각한 게 모듈러 연산이 제곱에서도 성립하니 제곱에 제곱을 하는 방식으로 조금 더 빠르게 풀 수 있을 것 같았다. 그래서 제곱을 처리하는 모듈러 연산을 알아보던 중 칸 아카데미에서 잘 정리한 글을 찾을 수 있었다.

 

https://ko.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/fast-modular-exponentiation

빠른 모듈로 거듭제곱법 (개념 이해하기) | 암호학이란? | 칸아카데미

처음에는 2의 거듭제곱인 경우를 떠올려서, 73이면 64 까지 계산하고 8, 1 을 기억했다가 붙여주는 방식으로 하려 했는데, 이 글에 나온대로 이진수를 이용해서 처리하는게 예뻐보였다. 근데 예제 넣어보니까 b%2 가 0이어도 계속 a 에 더해졌다. 보니까 for 문의 초기값은 for문이 시작할 때 단 한번만 실행되는데 거기다 i=b%2 라고 넣어놔서 계속 더해진 거였다 ㅋㅋ. 그래서 for 문 안에 따로 선언해 해놨다. 얼마전에 모듈러 연산 알게되면서 정리한 거 있는데 시간날 때 거듭제곱까지 한꺼번에 정리해서 올려야겠다.

 

 

문제 코드

---

#include <iostream>

using namespace std;

int main(void)
{
	unsigned long long a,b,c,exp_res;
	cin>>a>>b>>c;
	
	exp_res = a%c;
	
	if(exp_res!=0)
	{
		a=1;
		for(; b!=0; b=b>>1)
		{
			if(b%2)
				a = a * exp_res % c;
			
			exp_res = exp_res * exp_res % c;
		}
	}
	
	cout<<a%c<<'\n';
}