[알고리즘] 1629번: 곱셈

0. 문제

 

1629번: 곱셈

문제

자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 A, B, C가 빈칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.

출력

첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.

예제 입력 1

10 11 12

예제 출력 1

4

 

---

1. 문제 이해

 

A B C = 10 11 12라면…

1. 10 * 10 = 100 = 12 * 8 + 4 ← 12의 제곱은 12로 나눠 떨어지기 때문에 4만 남긴다.
2. 4 * 10 = 40 = 12 * 3 + 4
3. 4 * 10 = 40 = 12 * 3 + 4
4. ...
5. ...
6. ...
7. ...
8. ...
9. ...
10. ...
11. 4 * 10 = 40 = 12 * 3 + 4

 

A B C = 7 8 9 라면 …

1. 7 * 7 = 49 = 9 * 5 + 4
2. 4 * 7 = 28 = 9 * 3 + 1
3. 1 * 7 = 7 = 7
4. 생략… 4
5. 생략… 1
6. 생략… 7
7. 생략… 4
8. 생략… 1

• A를 제곱할 때마다 C로 나머지만 남긴다.
• 나머지에 다시 A를 곱한다.
• 이때 2,147,483,647 이하의 자연수의 제곱을 담을 수 있는 자료형을 사용한다. → long long(= _int64)

 

---

2. 제출

 

가. 시간 초과

// 백준 1629번: 곱셈
#include <iostream>

using namespace std;

int a, b, c;
long long ret;

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

	cin >> a >> b >> c;
	ret = a;
	for(int i = 0; i<b; i++){
		ret *= a;
		ret %= c;
	}
	cout << ret << "\\n";
	return 0;
}

9 10 11
a %= c : 9
0 : 4
1 : 3
2 : 5
3 : 1
4 : 9
5 : 4
6 : 3
7 : 5
8 : 1
9 : 9
9

시간을 줄이기 위해서는 b를 줄여야 한다.

 

4 3 5 1 9 다섯 숫자가 반복된다.

 

b를 5로 나눈 나머지를 구한다.

 

다섯 숫자 중 나머지 번째에 위치한 수가 답이다.

 

이것을 일반화 시켜보자.

 

---

나. 메모리 초과

 

// 백준 1629번: 곱셈
#include <iostream>
#include <vector>

using namespace std;

int a, b, c, tmp, repeat;
long long ret;
vector<int> v;

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

	cin >> a >> b >> c;
	ret = a; 
	for(int i = 0; i<b; i++){
		ret *= a;
		ret %=c;
		//cout << i << " : " << ret << "\\n";
		if(i==0){
			tmp = ret;
			v.push_back(ret);
		}else if(tmp == ret){
			repeat = i;
			break;
		}else{
			v.push_back(ret);
		}
	}
	//cout <<  "repeat : " << repeat << "\\n";

	b%=repeat;
	ret = v[(b+v.size()-1)%v.size()];
	cout << ret << "\\n";
	return 0;
}

• repeat : ret가 반복되는데 걸리는 간격
• b%=repeat : 불필요한 반복을 줄인다.

 

메모리가 부족하면 vector에 저장 안 하면 된다.

 

array를 사용한다.

 

a가 2이고 b, c가 2,147,483,647일 때 가장 많은 공간이 필요하다.

 

 

그렇기 때문에 대략 32개 이상으로 array를 선언하자.

 

a, b, c : 3 2147483647 2147483647면 안 된다.

3 2147483647 2147483647
repeat : 715827882
9

 

---

다. 수정

//백준 1629번: 곱셈
#include <iostream>

using namespace std;
typedef long long ll;
ll a, b, c;
ll go(ll a, ll b){   //재귀함수 + 모듈러 연산
	if(b==1) return a % c;
	ll ret = go(a, b/2);
	ret = (ret * ret) % c;
	if(b % 2) ret = (ret * a) % c; // 홀수라면 a 한번더
	return ret;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> a >> b >> c;
	cout << go(a, b) << "\\n";
	return 0;
}

직접 a^b를 계산하면 매우 큰 수가 되므로, 계산 과정에서 모듈러 연산을 사용하여 결과를 작게 유지합니다.

(앞선 방법에서 ret를 c로 계속 나누는 것과 같은 이유)

 

모듈러 연산의 분배 법칙을 사용하는 이유

1. 계산 효율성: a^b를 직접 계산하는 것은 비효율적입니다. 그러나 모듈러 연산의 분배 법칙을 사용하면 중간 계산 결과를 작게 유지할 수 있습니다. 이로 인해 계산 시간이 크게 줄어듭니다.
2. 오버플로우 방지: 컴퓨터에서는 정수의 크기에 제한이 있습니다. 큰 수의 거듭제곱을 계산하면 오버플로우가 발생할 수 있습니다. 모듈러 연산을 사용하면 중간 계산 결과를 작게 유지하여 오버플로우를 방지할 수 있습니다.

 

• a, b, c의 크기가 int의 범위에 포함되지만 굳이 long long을 사용하는 이유
  : ret = (ret * ret) % c; 와 같이 계산 과정에서 int의 범위를 넘겨버림.

 

보충 설명 : 모듈러 연산

 

모듈러 연산은 나눗셈 연산에서의 나머지를 구하는 연산입니다.

 

"mod" 또는 "%" 기호로 표시되며, 특정 숫자를 다른 숫자로 나누었을 때의 나머지를 반환합니다.

 

예를 들어, a를 b로 나누었을 때의 나머지를 구하는 모듈러 연산은 다음과 같이 표현됩니다 : a mod b

 

모듈러 연산의 몇 가지 특징:

1. a mod b의 결과는 항상 0 이상 b-1 이하입니다.
2. a mod b = a (단, a < b )
3. 덧셈, 뺄셈, 곱셈에 대한 분배 법칙이 성립합니다. 그러나 나눗셈에 대해서는 성립하지 않습니다.

// 암기 : 나머지를 제외한 분배 법칙이 적용됨.
1. [(a mod n)+(b mod n)]mod n=(a+b)mod n 
2. [(a mod n)-(b mod n)]mod n=(a-b)mod n
3. [(a mod n)(b mod n)]mod n=(a*b)mod n

 

간단한 예제:

• 7 mod 3 = 1 (7을 3으로 나누면 몫은 2, 나머지는 1)
• 10 mod 2 = 0 (10을 2로 나누면 나머지는 0)

 

---

 

• 23년 11월 16일 추가

나눠야 하는 수가 ...

1) 정해져 있을때  → 재귀함수를 통한 모듈러 연산
2) 변화할 때 → while문을 통한 모듈러 연산