알고리즘 문제를 풀다보면 결과 값이 너무 커져서 1,000,000,007로 나눈 나머지를 출력한다. 같은 조건을 제시하는 문제들이 종종 보인다.
과거에 이런 경우 이유는 이해못했지만 https://smallpants.tistory.com/64에 남겨둔 것처럼 (a+b)%n == ((a%n)+(b%n))%n라고 그냥 기억해두고 쓰고 있었다.
이번 기회에 이 내용을 정리해둔다.
모듈러 연산, 즉 나머지 연산도 분배법칙을 적용할 수 있다.
예를들어 분배법칙만 적용한다면 (A + B) % p = ((A % p) + (B % p)) 가 되는데
이 결과에 한번 더 모듈러 연산을 취해줘야해서
결과적으로 (A + B) % p = ((A % p) + (B % p)) % p 가 되는 것이다.
이게 가능한 이유는 A와 B를 p로 나눴을때의 몫과 나머지를 각각 [qa, ra], [qb, rb] 라고 했을 때
A = qa * p + ra
B = qb * p + rb 가 된다.
이때 위 두 식을 (A + B) % p 에 대입한다면 (qa * p + ra + qb * p + rb) % p가 되고
p를 정리하면 ((qa + qb) * p + ra + rb) % p가 된다.
이러면 (qa + qb) * p 부분은 p로 나머지연산할때 0이되므로 위 식은 (ra + rb) % p와 같다.
이때 ra = A % p, rb = B % p이므로 최종적으로 정리하면 ((A % p) + (B % p)) % p와 같다.
즉 이건 모듈러의 분배법칙때문에 생기는 현상이므로 A와 B의 합이건 차건 곱이건 다 적용된다. 다만 나머지는 좀 다르다.
(A + B) % p = ((A % p) + (B % p)) % p
(A * B) % p = ((A % p) * (B % p)) % p
차의 경우 음수가 나오는 경우를 방지하기 위해 p를 한번 더해준 후 나머지 연산을 취한다.
(A - B) % p = ((A % p) - (B % p) + p) % p
나눗셈에 대한 나머지연산은 분배법칙을 적용할 수 없다.
예를들어 A = 4, B = 2, p = 2라면 0 / 0 꼴이 되므로 0으로 나눌 수 없기 때문이다.
그래서 페르마의 소정리를 이용해서 나눗셈을 곱셈의 형태로 바꾸어서 해결 가능하다고 한다. 이건 수학적인 개념이라 정확히는 이해 못했지만 아래처럼 사용하면 될듯하다.
p가 소수이고, B가 정수일때 사용
(A / B) % p = (A * B^(p-2)) % p = ((A % p) * (B^(p-2) % p)) % p
※ 참고 문헌