[BAEKJOON] 1629번 : 곱셈 *

문 제

 

소 스  코 드

#include <iostream>

typedef long long INT;

void Remain_Num(const INT&, int, const int&, INT&);

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	INT A;
	int B, C;
	std::cin >> A >> B >> C;

	INT remain{ 1 };

	Remain_Num(A, B, C, remain);

	std::cout << remain;

	return 0;
}

void Remain_Num(const INT& a, int b, const int& c, INT& r) {
	INT temp{ a };
	while (b != 0) {
		if (b & 1) r = (r * temp) % c;
		temp = (temp * temp) % c;
		b >>= 1;
	}
}

 

풀 이

 

• 모듈러 연산

• 거듭제곱(나머지) 계산

나머지 계산시 반복되는 숫자를 통하여 구현하고 싶었지만,  너무 큰 수일 경우 너무 많은 수가 반복 되기 때문에, 틀렸다는 결과가 나왔다.

거듭제곱 성질과 나머지의 성질인 모듈로 연산의 성질과 증명을 찾아본 결과,

( A x B ) % C = ( A % C x B % C ) % C 라는 분배법칙의 성립을 알 수 있었습니다.

이를 통하여,

B가 짝수 일 경우,

B가 홀수 일 경우,

라는 공식을 통하여 결과를 찾을 수 있다.

 

출 력 값

 

 

문 제  출 처

문제 링크 : https://www.acmicpc.net/problem/1629

1629번: 곱셈