[연산자]나머지 연산과 분배법칙

APS과정에서 연산의 결과가 long을 넘는 아주 큰 수에 대한 사칙 연산이 필요한 경우가 있다. 당연히 overflow가 발생하기 때문에 결과 처리가 상당히 어렵다.

long a = Long.MAX_VALUE -1;
long b = Long.MAX_VALUE -1;
System.out.println(a + b); // -4

 

그래서 특정 수로 나눈  나머지를 구하라는 문제가 자주 등장한다.

// 합을 1007로 나눈 나머지를 출력하시오.
System.out.println((a + b) / 1007)     ?

 

하지만 위와 같은 경우도 a+b가 연산되는 과정에서 이미 overflowr가 발생하므로 원하는 답을 얻기 어렵다.

 

이런 경우 나머지 연산자의 분배 법칙을 이용해야 한다. 각각 %를 취한 후 다시 전체적으로 %를 구한다.

(A+B)%M = ( (A%M) + (B%M) ) %M

(A*B)%M = ( (A%M) * (B%M) )%M

(A-B)%M = ( (A%M) - (B%M) + M ) %M

특히 뺄셈의 경우 음수가 나올 수 있기 때문에 M을 한번 더해준 후 나머지를 구한 부분을 기억해두자.

 

하지만 사칙 연산 중 나눗셈에 대한 나머지 연산은 분배 법칙이 적용되지 않는다. 이를 위해서는 페르마의 소정리를 이용해서 분모를 분자로 올려야 한다.

 

https://soeasyalgo.tistory.com/12