사용자 도구

사이트 도구


ps:모듈러_연산

모듈러 연산

  • 덧셈, 뺄셈, 곱셈은 간단하다. 그냥 연산 한번 할때마다 모듈러를 취하면 된다
    • (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 = 1) % 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가 모듈러 역원이다. 일반적으로는 이 방법이 위의 방법보다
  • 파이썬에서는 따로 구현할 필요 없이 pow(x, -1, MOD) 를 사용하면 된다.

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

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])
1)
a % M) * inv(b % M

토론

댓글을 입력하세요:
A R G I K
 
ps/모듈러_연산.txt · 마지막으로 수정됨: 2021/01/21 04:54 저자 teferi