gmldk728   3년 전

문제를 풀다 궁금한 점이 생겨서 질문드립니다.

간혹 가다가 문제에서 int 범위가 넘어갈 만큼 큰 수를 요구할 때 11041번 문제와 같이 '1,000,000,007로 나눈 나머지를 출력한다.' 이런식으로 문제를 출제하는데 마지막에서만 1,000,000,007를 나누면 int범위를 넘어 오버플로우로 인해 이상한 값이 출력된다는 것은 압니다. 그래서 계산 중간에도 1,000,000,007를 나누어주어야 하고요

그런데 수학적으로 접근하면 곱셈과 나머지만 있는 식의 경우 분배법칙이 되지 않아 나누기를 한번 할 것을 두번 하면 값이 달라지지 않나요??

ychangseok   3년 전

(a*b) mod p = ((a mod p) * (b mod p )) mod p 입니다.

a = A*p + A'

b = B*p + B'로 두면 (0 <= A', B' < p)

a mod p = A'. b mod p = B'입니다.

따라서, 위 식의 우변은 (A'*B') mod p가 됩니다.

a*b = A*B*p*p + (A*B'+A'*B)*p + A'*B'이므로

(a*b) mod p = (A' * B') mod p 입니다.

따라서, (a*b) mod p = ((a mod p) * (b mod p )) mod p가 성립하게 됩니다.

댓글을 작성하려면 로그인해야 합니다.