[BOJ] 1629 | 곱셈

1629 | 곱셈
https://www.acmicpc.net/problem/1629

 

 

 

 

 

작성 코드

 

 

#include <iostream>
using namespace std;
int main() {
  unsigned long long a, b, c;
  cin >> a >> b >> c;
  unsigned long long res = 1;
  for(unsigned long long i = 0 ; i < b ; i++) {
    res *= a;
    res %= c;
  }
  cout << res;
}

 

 

접근 방법

 

1. 모듈러 연산을 이용

 

• 시간 초과 발생

 

 

#include <iostream>
using namespace std;
int main() {
   unsigned long long a, b, c;
    cin >> a >> b >> c;
    int res = 1;
    if ((c % 2 == 1) & (b % 2 == 1)) {
            res = a % c;
    } else {
        res = a * a % c;
    }
    cout << res;
}

 

접근 방법

 

1. 첫번째 코드에 여러가지 답을 넣어보며 패턴을 분석해보니, 나머지가 반복됨을 알 수 있었음
2. (위에 작성한 코드는 아니지만) '곱하는 횟수 % 반복되는 수의 길이' 가 답이지 않을까 -> 몇 개는 맞지만 몇 개는 오답이었음

 

 

이상 코드

 

 

#include <iostream>
using namespace std;
long long a, b, c, k;

long long power(long long b) {
	if (b == 0) return 1;
	if (b == 1) return a % c;
	
	k = power(b / 2) % c;
	if (b % 2 == 0) return k * k % c;
	return k * k % c * a % c;
}

int main(void) {
	cin >> a >> b >> c; 
	cout << power(b);

	return 0;
}

// [출처] https://velog.io/@junttang/BOJ-1629-%EA%B3%B1%EC%85%88-%ED%95%B4%EA%B2%B0-%EC%A0%84%EB%9E%B5-C

 

• 분할 정복 + 모듈러 연산 사용
• 불필요한 재귀연산 최소화

 

 

 

거듭 제곱과 관련된 분할 수식

 

• b가 짝수이면 : a^b = a^(b/2) x a^(b/2)
• b가 홀수이면 : a^b = a^(b/2) x a^(b/2 + 1)