지수법칙 & 모듈러 연산

알고리즘 문제를 풀다가 지수법칙과 모듈러 연산에 관한 수학적인 문제가 나와 기억하기 위해 작성한다.

지수법칙(거듭제곱의 곱)

지수법칙은 다음과 같다.

$$x^{n} \ast x^{m} = x^{n+m}$$

 

ex) $x^8$ 지수가  짝수일 때 즉, $x^8 = x^{4+4}$

= $x^4 * x^4$

= $(x^2 * x^2) * (x^2 * x^2)$

= $((x^1 * x^1) * (x^1 * x^1)) * ((x^1 * x^1) * (x^1 * x^1))$

 

ex) $x^9$ 지수가  홀수일 때 즉, $x^9 = x^{4+4} * x$

= $x^4 * x^4 * x$

= $(x^2 * x^2) * (x^2 * x^2) * x$

= $((x^1 * x^1) * (x^1 * x^1)) * ((x^1 * x^1) * (x^1 * x^1)) * x$

 

위와 같은 식이 성립된다.

모듈러 연산(Modular arithmetic)

모듈러 연산은 3가지의 특징을 가지고 있다.

 

1. 모듈러 연산 덧셈 성질은 다음과 같다.

$$(A + B) \bmod{C} = (A \bmod{C} + B \bmod{C}) \bmod{C}$$

2. 모듈러 연산 뺄셈 성질은 다음과 같다.

$$(A - B) \bmod{C} = (A \bmod{C} - B \bmod{C}) \bmod{C}$$

3. 모듈러 연산 곱셈 성질은 다음과 같다.

$$(A * B) \bmod{C} = (A \bmod{C} * B \bmod{C}) \bmod{C}$$

 

"A와 B를 더한 후에 모듈러 연산을 수행한 값"과 "A, B 각각에 대해 모듈러 연산을 수행하고 더한 값에 다시 모듈러 연산을 한 값과 같다"는 의미이다.

 

구현(C++)

백준 1629 곱셉

 

이 문제는 시간제한이 0.5초로 단순히 a를 b번 곱하고 c로 나머지 값을 구하면 시간 초과가 발생한다.

또 a, b, c가 21억 이하의 자연수로 최대 값이면 타입의 범위를 초과한다.

그래서 분할 정복을 이용한 거듭제곱인 지수법칙으로 시간을 줄이고 범위를 넘지 않도록 모듈러 연산으로 값을 작게 만들어준다.

#include <bits/stdc++.h>
using namespace std;
#define FAST_IO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
typedef long long ll;
ll a, b, c, ans=1;
int main(){
    FAST_IO;
    cin >> a >> b >> c;
    while(b){
        if(b&1) ans=ans*a%c;
        a=a*a%c;
        b/=2;
    }
    cout << ans;
    return 0;
}

 

 

 

🔗 Reference

• LaTex 수식 온라인 에디터
• 백준 - 1629번 곱셈