나머지 분배법칙(모듈러 연산)

백준 문제의 경우 숫자가 큰 값이 자주 사용되는데, 문제에서 미리 어떤 수로 나누라고 지시를 한다.

그러면 모든 계산을 끝나고 나머지를 나누면 또 시간초과로 틀리게된다.

이 경우 연산하는 과정에서 계속 나머지를 나눠주면 된다.

이 방법이 나머지 분배법칙.

 

 

나머지 분배법칙(모듈러 연산)

(A + B) % p = ((A % p) + (B % p)) % p
(A * B) % p = ((A % p) * (B % p)) % p
(A - B) % p = ((A % p) - (B % p) + p) % p

 

어떤 수를 다른 숫자로 나눈 나머지를 구하는 연산.

Modular arithmetic이라고 하는데 이를 줄여서 Mod라고 부른다.

 

나누기의 경우는 없는데 페르소마 정리를 사용해야 한다고 한다... 생략함