[C++] 모듈러 사칙 연산 (BOJ 1629: 곱셈)

백준 1629: 곱셈 문제를 풀다가 자꾸 시간초과가 나오다보니 결국 하는 방법을 찾게 되었는데 모듈러 계산에 대해서 공부할 필요성을 느끼게 되었다. 앞으로 모듈러 연산이 나올 때마다 여기다가 다시 정리를 해야겠다.

 

모듈러 사칙 연산

덧셈, 뺄셈, 곱셈에 대해서는 다음 식이 항상 성립한다. (이부분에서는 mod M을 % M이라고 표현)

• 덧셈 : (a+b) % M = ((a % M) + (b % M)) % M
• 뺄셈 : (a-b) % M = ((a%M) - (a%M)) % M
• 곱셈 : (a*b) % M = ((a%M) * (b%M)) % M

나눗셈 : 모듈로 연산에서 나눗셈은 곱셈 역원(multiplicative inverse)을 곱하는 방식으로 이루어진다.
모듈로 곱셈 역원은 항상 존재하는 것이 아니라, b와 M이 서로소(coprime)일 때만 존재한다

 

항상 모듈러 연산을 할 때마다 이게 가능한 것인지 고민하곤 했는데 이 성질을 기억하고 막힘 없이 써먹으려고 한다. 

 

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

1629번: 곱셈

 

풀이 방법? 

입력을 받는 수가 매우 크고 시간 제한이 있는 경우에, 특히 나머지나 특정 수열과 같은 연산을 해야하는데 그 값이 매우 큰 경우에는 Divid & Conquer을 이용해 분할 정복을 해야한다. 분할 정복은 Dynamic Programming의 개념이 되는 부분이라고도 할 수 있는데 차이점으로는 도달한 값을 따로 저장하지 않고 재귀적으로 돌면서 값을 찾는 것이다.

 이 문제 역시 모듈러 연산과 이러한 분할 정복을 통해 문제를 풀 수 있다. DP에서는 점화식을 찾았던 것 처럼 분할 정복에서는 분할 수식을 찾는 것이 중요하다. 이 문제의 분할 수식은 아래와 같다.

 

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

 

구현

그 후 모듈러 연산을 해주어서 식을 정리해주면 되는데, 

 

calculate(n)%b=(calculate(n/2)%b*calculate(n/2)%b)%b를 (n이 짝수일 때)

calculate(n)%b={(calculate(n/2)%c)*(calculate(n/2)%c)}%c ((tmp*tmp)%b)

n이 홀수일 때는

(tmp*tmp%b)*(a%b)으로 만들어주면 된다.

 

사실 모듈러 공식상으로는 

{(tmp*tmp%b)*(a%b)}%b가 맞는 것 같은데 이렇게 사용하면 틀렸다고 나온다.

 

소스코드!

#include <iostream>
#include <algorithm>
#include<bits/stdc++.h>
#include<queue>
#include<limits.h>
#include<map>

using namespace std; //모든 식별자가 고유하도록 보장하는 코드 영역
long long int a,n,b;

long long calculate(long long n)
{
  if(n==0)
    return 1;
  if(n==1)
    return a%b;

  int tmp=calculate(n/2)%b;

  if(n%2==0)
    return (tmp*tmp)%b; // {(calculate(n/2)%c)*(calculate(n/2)%c)}%c
  else
    return (tmp*tmp%b)*(a%b);//(tmp*tmp)%b*(a%b);//(tmp*tmp*(a%b))%b;
      
}

int main() {
  
  cin>>a>>n>>b;
  int result=calculate(n);
  cout<<result;
}