45. Modular Operation

모듈러 산술(Modular Arithmetic)은 정수를 특정한 모듈러 $m$으로 나눈 나머지로 정의하는 방법이다. ($m$은 $2$ 이상의 정수) 이 구조에서 실행되는 연산들을 모듈러 연산(Modular Operation)이라고 한다.

 

수학에서 $a$를 $b$로 나눈 나머지는 보통 $\color{#0000FF}{a \,\bmod\, b}$로 표기하고, $a$와 $b$를 $m$으로 나눈 나머지가 같을 경우 $\color{#0000FF}{a \equiv b \pmod{m}}$이라고 표기하며 이를 합동식(Congruence)이라고 한다. 대부분의 프로그래밍 언어에는 정수 나눗셈의 나머지를 구하는 $\text{%}$ 연산자가 존재하여 $a \,\bmod\, b$ 대신 $a\text{%}b$를 사용하게 된다.

 

모듈러 연산에서 가장 기본이 되는 법칙들은 다음과 같다.

• $(a-m)\text{%}m = a\text{%}m = (a+m)\text{%}m; a-m \equiv a \equiv a+m \pmod{m}$
• $a\text{%}m + b\text{%}m \equiv (a+b)\text{%}m \pmod{m}$
• $a\text{%}m - b\text{%}m \equiv (a-b)\text{%}m \pmod{m}$
• $a\text{%}m \times b\text{%}m \equiv a \times b\text{%}m \pmod{m}$
• $(-a)\text{%}m \equiv -(a\text{%}m) \pmod{m}$

많은 프로그래밍 언어의 경우 음수에 $\text{%}$ 연산을 하면 결과값이 음수가 나올 수 있으며 이것이 문제가 되는 경우도 발생할 수 있으므로 모듈러 연산을 할 때는 음수가 최대한 등장하지 않도록 하는 것이 좋다. 가장 많이 발생하는 실수는 빼기 연산을 할 때 결과값이 음수가 될 수 있는 코드를 작성하는 것이다. 다음의 두 코드는 결과값이 음수가 될 수 있는지의 여부에 차이가 있다.

------------------------------------

s = (a % m - b % m) % m;

------------------------------------

s = (a % m - b % m + m) % m;

------------------------------------

위의 코드는 $a\text{%}m$이 $b\text{%}m$보다 작다면 결과값이 음수가 될 수 있다. 하지만 $a\text{%}m - b\text{%}m$의 최솟값이 $-m+1$이므로 여기에 $m$을 더하면 괄호 안의 값은 항상 $1$ 이상이다. 따라서 밑의 코드의 결과값은 항상 $0$ 이상이 된다.

 

또 하나 많이 발생하는 실수는 세 개 이상의 값을 곱할 때 오버플로우가 날 수 있는 코드를 작성하는 것이다. 각각의 변수가 부호 있는 $8$바이트 정수 자료형이라고 할 때, 아래의 코드는 $m$이 $2^{21}$보다 커질 경우 오버플로우가 발생할 가능성이 생긴다.

s = a * b * c % m;

오버플로우가 발생하지 않게 하기 위해서는 아래 코드와 같이 각각의 곱하기 연산 뒤에 $\text{%}$ 연산을 넣어야 한다.

s = a * b % m * c % m;

이 코드 역시 $m$이 $2^{32}$보다 커질 경우 오버플로우가 발생할 가능성이 생기지만, 모듈러 연산이 필요한 대부분의 문제에서 $m$은 $2^{32}$보다 작은 값으로 주어지므로 이 정도로 충분하다.

---

모듈러 연산 중 나눗셈은 다른 산술 연산들에 비해 복잡하다. 모듈러 연산의 결과값은 정수로 나와야 하기 때문에 그냥은 나눌 수 없는 경우도 자주 발생한다. 기본적으로 $a \times b\text{%}m = c$일 경우 $c/b = a$라고 할 수 있는데, 약간의 예외가 생기기도 한다. $\gcd(m, b) = k$라고 할 때,

 

A. $k = 1$인 경우

이때는 항상 $c/b = a$가 성립한다.

 

B. $k > 1$인 경우

이때는 항상 $c/b = a$라고 하기 애매하다. $m = m'k, b = b'k$라고 하면,

$(a+m') \times b\text{%}m = (ab+m'b)\text{%}m = (ab+m'b'k)\text{%}m = (ab+b'm)\text{%}m = ab\text{%}m = c$이므로 $c/b = a+m'$이라고 해도 틀리지 않는 것처럼 보인다. 실제로 이 등식은 틀린 것이 아니다. 단지 $c/b$의 결과값이 여러 개 존재할 수 있는 것이다. 반대로 어떤 정수 $d$가 존재하고 $d$가 $k$의 배수가 아니라면 $d/b$의 결과값은 존재하지 않는다. 나눠지는 수에 따라 결과값이 여러 개가 될 수도 있고 존재하지 않을 수도 있기 때문에 이 경우 모듈러 나눗셈을 정의하는 것은 간단하지 않은 문제가 된다.

 

이러한 이유로 대부분의 문제들에서는 모듈러 나눗셈이 필요한 경우 $m$이 큰 소수로 주어진다.

 

$m$이 소수인 경우, $a/b$의 결과값을 계산할 때는 페르마의 소정리를 이용한다. 페르마의 소정리에 의하면 $a/b = ab^{p-1}/b = ab^{p-2}$와 같고, $b^{p-2}$를 분할 정복을 이용한 거듭제곱을 이용하여 계산하면 $a/b$를 구할 수 있다. 실제 산술 연산과 성격이 약간 다르기 때문에 모듈러 나눗셈 대신 모듈러 곱셈 역원(Modular Inverse)이라는 용어를 사용하는 경우가 많다. 구현은 다음과 같다.

typedef long long LL;
LL modinv(LL x, LL y, LL m)
{
    LL p = m - 2;
    for(; p; p >>= 1)
    {
        if(p & 1)x = x * y % m;
        y = y * y % m;
    }
    return x;
}

소수 모듈러 중 가장 자주 등장하는 것은 $1000000007(10^9+7)$과 $998244353$이다. 해당 모듈러들에 익숙해지는 것이 좋다.

 

$m$이 소수가 아니더라도 $\gcd(m, b) = 1$이라면 $a/b$의 결과값이 하나로 정해지고, 이를 구하는 방법은 $m$이 소수인 경우와 비슷하지만, $b$의 지수가 $p-2$가 아닌 다른 수가 된다. 이 값은 오일러 토션트 함수를 이용해서 구할 수 있다.

 

[연습문제]

 

BOJ 13172. Σ (Silver I)

$S_i/N_i$를 다 더하면 된다.

 

→ solved.ac tag: modular_multiplicative_inverse