1629번 곱셈

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

1629번: 곱셈

1629번 곱셈 문제만 보면 정말 단순해 보인다. 그냥 B번만큼 곱한 후 C로 나눠주면 된다. 여기서 생각해볼 점은

 

A^B = A^(B/2) * A^(B/2)이라는 것이다. 홀수면 A^(B/2) * A^(B/2) * A이다. 그래서 재귀로 해결해도 된다.

 

또 다른 방법은 

B를 2로 나누어 주면서 나머지가 홀수 일때만 결과값에 곱해주고 나머지는 계속 A값을 곱해가면 된다.

 

그리고 여기서 C로 나누어주어야하는데 마지막 결과값에 나누어주면 long  long 형도 버틸 수 없는 큰 값이 될 것이다. 그래서 계산 중간중간에 곱하는 연산이 있을 때 마다 계속 나누어주어야한다. 

 

방법 1.

#include <cstdio>
#include <math.h>

long long getPower(long long A, long long B, long long mod);

int main(){
	long long A, B, C;
	scanf("%lld %lld %lld", &A, &B, &C);
	printf("%lld", getPower(A, B, C)%C);
}

long long getPower(long long A, long long B, long long mod){
	if(B == 0)
		 return 1;
	long long temp = (getPower(A, B/2, mod));

	if(B % 2 == 0)
		return (temp%mod * temp%mod) % mod;
	else 
		return (temp%mod * temp%mod * A)%mod;
}

방법 2.

#include <cstdio>

long long getPower(long long A, long long B, long long mod);

int main(){
	long long A, B, C;
	scanf("%lld %lld %lld", &A, &B, &C);
	printf("%lld", getPower(A, B, C)%C);
}

long long getPower(long long A, long long B, long long mod){
	long long temp = 1;

	while(B > 0){
		if(B%2!=0){
			temp*=A;
			temp%=mod;
		}
		A*=A;
		A%=mod;
		B/=2;
	}

	return temp%mod;
}