모듈러 연산 (Modular arithmetic)

덧셈, 뺄셈, 곱셈은 간단하다. 그냥 연산 한번 할때마다 모듈러를 취하면 된다
- (X + Y) % M = ( (X % M) + (Y % M) ) % M
- (X - Y) % M = ( (X % M) - (Y % M) + M) % M (X>Y 일때)
- (X * Y) % M = ( (X % M) * (Y % M) ) % M

모듈러 나눗셈

(a / b) % M 은 저 방식으로 계산할 수 없다.
b와 M이 서로소이면, b의 모듈러 역원 inv(b)를 계산한 뒤, 이것을 곱하는 방식으로 구할 수 있다
- (a / b) % M = (a * inv(b)) % M = ((a % M) * inv(b % M)) % M
b와 M이 서로소가 아니면, 모듈러 역원이 존재하지 않아서 저 방식으로는 불가능하다.. 만약에 a나 b값을 계산하는 과정에서 정확한 값을 계산하지 못하고, a%M이나 b%M만 계산했다면, 이것으로는 (a/b)%M 을 구하는 것이 불가능하다.
- 그래서 이런 상황을 피하기 위해서, 보통 문제에서는 M을 매우 큰 소수로 준다.
- 그럼에도 이런 계산을 해야 하는 상황이 닥친다면 취할수 있는 방법이..
  - a와 b가 모두 어떤 수들의 곱으로 구해지는 값이라면, a와 b를 소인수분해된 형태로 계산한다. 그러면 biginteger을 쓰지 않고도 a와 b의 정확한 값을 들고 있을수 있고, a/b도 계산 가능하다. 이렇게 a/b의 실제 값을 구한 다음에 모듈러를 취한다.
  - b만 어떤 수들의 곱으로 구해지는 값이라면, b를 소인수분해해서 p1^e1 * p2^e2 * pn^en의 형태로 만든 다음에, a % (p1^e1), a % (p2^e2), …, 을 각각 구한다. 그리고 중국인의 나머지 정리를 적용한다.

모듈러 역원 (Modular multiplicative inverse)

Modular multiplicative inverse 를 참고. 간단하게 말하면, a의 M에 대한 모듈러 역원은 (a * b) % M = 1 이 되는 b를 말한다
- a와 M이 서로소일때만 정의된다.

어떤 수 a의 역원 구하기

이것을 구하는 방법은 두 가지가 있다. 페르마의 소정리를 이용하는 방법과 확장 유클리드 알고리즘을 사용해서 구하는 방법.
페르마의 소정리를 응용하는 방법은 M이 소수일때만 가능하다. a^(M-2) % M 을 계산하면 되는데, 분할정복을 이용한 거듭제곱 방법을 사용하면 O(logM)에 계산 가능하다.
- 원칙적으로는 페르마의 소정리의 일반형태인 오일러 정리를 사용하면 소수가 아닌 M에 대해서도 a^(φ(M)-1) % M 을 계산해서 구할수 있지만, 이렇게 되면 오일러 피 함수를 계산하기 위해서 소인수분해를 또 해줘야 한다. 그래서 실질적으로는 φ(M)=M-1으로 바로 구할수 있는 M이 소수인 경우에 대해서만 사용하는 것.
확장 유클리드 알고리즘을 사용하는 방법은, a*x+M*y = GCD(a, M) = 1 의 해 x를 구하는 것이다. 이 식을 정리하면 ax - 1 = (-y)M이고 즉, (a*x)%M=1 이 되므로 x가 모듈러 역원이다. M이 소수가 아니어도 쓸수 있다.
파이썬에서는 따로 구현할 필요 없이 pow(x, -1, MOD) 를 사용하면 된다.

n개의 수, [a_1,..,a_n] 에 대한 역원 구하기

O(logM)의 역원 연산을 n번 반복하여 O(nlogM)에 계산하는 대신에, O(n+logM)에 구할 수 있는 방법이다.
https://en.wikipedia.org/wiki/Modular_multiplicative_inverse#Multiple_inverses

코드를 열심히 간단하게 만들어보면 이런식이 된다.

def multiple_mod_inv(nums, mod):    
    a = list(nums)
    b = [v := 1] + [v := v * x % mod for x in reversed(a)]
    b_inv = pow(b.pop(), -1, mod)
    return [b_inv * b.pop() % mod] + [
        (b_inv := b_inv * a_ % mod) * b_ % mod for a_, b_ in zip(a, reversed(b))
    ]

근데, 모듈러 역원 연산이 원래 빠른 편이기 때문에, 실제 속도에서 차이가 나려면 n이 100,000정도는 되어야 한다.

Factorial값들 (1!, 2!, 3!, ..., n!) 에 대한 역원 구하기

역시 위와 비슷한 원리로, 역원 계산은 한번만 하고, 나머지 값들에 대한 역원은 곱셈만을 사용해서 구하는 O(n+logM) 방법이다.
factorial 값들을 다 만들어서 리스트에 저장해놓고 multiple_mod_inv를 돌려도 시간복잡도는 똑같지만.. 이게 2배정도 빠르다
- 2배라고는 해도.. 이게 실제 속도에서 차이가 나려면 n이 1,000,000 정도는 되어야 하긴 하다..

def factorial_mod_inv(n, mod):
    """Returns mod inverses of factorials, [inv(0!), inv(1!), .., inv(n!)]."""
    fact = 1
    for i in range(1, n + 1):
        fact = fact * i % mod
    v = pow(fact, -1, mod)
    finv = [v] + [v := v * i % mod for i in range(n, 0, -1)]
    return finv[::-1]

n이하의 모든 수, [1, ..., n] 에 대한 역원 구하기

$ \text{inv}[i] = - \left\lfloor \frac{m}{i} \right\rfloor \cdot \text{inv}[m \bmod i] \bmod m $ 의 공식을 이용하면 1부터 n까지의 모든 수에 대한 모듈러 역원을 O(n)에 계산 가능하다. 코드도 간단하다.
- ```
inv = [None, 1]
for i in range(2, n):
    inv.append(-(MOD // i) * inv[MOD % i])
```

목차

모듈러 연산 (Modular arithmetic)

모듈러 나눗셈

모듈러 역원 (Modular multiplicative inverse)

어떤 수 a의 역원 구하기

n개의 수, [a_1,..,a_n] 에 대한 역원 구하기

Factorial값들 (1!, 2!, 3!, ..., n!) 에 대한 역원 구하기

n이하의 모든 수, [1, ..., n] 에 대한 역원 구하기