[C/C++ 백준 1629번] 곱셈 (Silver 1)

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

1629번: 곱셈

보자마자 while문 써서 해봤는데, 당연히 시간초과가 나온다. 지수의 범위가 엄청 크니 그럴만도 하다.

그래서 생각한건, A의 1승, 2승, 4승, ... 의 배열을 만들어, B를 이진수로 표현한뒤 배열의 원소의 곱으로 표현하는 방법이다. 과정에서 int형 범위끼리 곱해야하므로 long long int를 이용해야 한다 (나는 자연수 조건이라 unsigned도 사용했다.).

 

#include <cstdio>
int main(void){
	unsigned long long int A, B, C, ans=1, cnt=0;
	scanf("%llu %llu %llu",&A,&B,&C);
	unsigned long long int twoB[40]={A,};//A의 1승, 2승, 4승.. 담는배열 
	for(int i=1; i<=31; i++){
		twoB[i]=(twoB[i-1]*twoB[i-1])%C;
	}
	while(B>0){
		if(B%2==1)	ans *= twoB[cnt];
		ans = ans % C;
		B=B/2;
		cnt++;
	}
	printf("%llu",ans);
}