[재귀] 1629 - 곱셈

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

1629번: 곱셈

 

문제분석

모든 변수의 범위가 int형이라 long long int로 대충 계산해도 오버플로우가 난다

전혀 감을 못잡겠어서 강의 보았다

아무리 봐도 이해가 안돼서 찾아봤는데 모듈러 연산 공식을 사용함

모듈러 연산에 대해 알고 있어야 강의도 이해할 수 있음

≡ : 모듈러 합동

3(mod 67) : (mod 67)의 3번째 사이클

ex) 11^12 mod 13

→ 11^2 mod 13 = 121 ≡ 4 (mod 13)

→ 11^4 mod 13 = (11^2)^2 ≡ (11^2 mod 13)^2 ≡ 4^2 ≡ 3 (mod 13)

→ 11^8 mod 13 = (11^4)^2 ≡ (11^4 mod 13)^2 ≡ 3^2 ≡ 9 (mod 13)

→ 11^12 mod 13 = 9*3 ≡ 1 (mod 13) ⇒ 11^12 mod 13 = 1

알고리즘_1

1. 특정 지수의 제곱 mod를 쉽게 구한다면 B가 몇이든 구할 수 있을 것 같다
2. B를 2진수로 변환한다
3. [ A mod C, A^2 mod C, A^4 mod C, A^8 mod C, … , (A^2)^31 mod C ] 를 구한 값을 배열에 저장
4. B를 LSB 부터 검사하며 자릿수가 1인 경우인 index의 모든 값을 곱한 뒤 mod C를 한다

알고리즘_2

1. 재귀를 이용해 구한다
2. A^B mod C에서 B가 짝수일 경우 (A^(B/2) mod C)^2 mod c
3. A^B mod C에서 B가 홀수일 경우 ((A^(B/2) mod C)^2 * A) mod c
4. B가 1일 경우 A mod C를 반환

알고리즘_1

#include <iostream>
#include <string>

std::string bin(int num){
	std::string bin = "";
	while(num != 0){ //Little Endian
		if(num % 2 == 1)
			bin.append("1");
		else
			bin.append("0");
		num /= 2;
	}
	return bin;
}

int main(void){
	long long int a, b, c;
	std::cin >> a >> b >> c;
	std::string bin_b = bin(b);
	long long int arr[1000];
	arr[0] = a%c;
	arr[1] = (a*a)%c;
	int ans = 1;

	for (int i=2; i<32; i++)
		arr[i] = (arr[i-1] * arr[i-1])%c; //배열 값 출력해보면 재귀 방식이랑 같은 패턴 도출됨
	
	for (int i=0; i<bin_b.length(); i++){
		if(bin_b[i] == '1')
			ans = (ans * arr[i]) % c;
	}

	std::cout << ans << '\\n';
}

알고리즘_2

#include <iostream>

long long int calc(int a, int b, int c){ 
        if(b == 1) return a % c;
        long long int ret = calc(a, b/2, c); 
        ret = ret * ret % c;
        if(b % 2 == 0) return ret;
        return (ret * a) % c;
}

int main(void){
        int a, b, c;
        std::cin >> a >> b >> c;

        std::cout << calc(a, b, c) << '\\n';
}

회고

모듈러 연산의 특징을 몰랐다면 뺑뺑 돌아서 풀었을 것 같다

아마 못 풀었을 수도 있다

영어 잘하려면 단어가 중요한 것처럼 코딩 수학을 틈틈이 익혀야겠다