나머지 연산 시 오버플로우 주의사항

(a * b)를 c로 나눈 나머지 연산을 할 때 보통 (a * b) % c로 먼저 계산을 하고, 값이 커질 때 (((a % c) * (b % c)) % c)를 하게 되는데, 결과값이 long long 자료형을 받는다면 문제가 되지 않는다. 단 a, b, c는 정수라는 가정이 있다

 

a, b, c는 나머지 연산을 한다면 최소 21억보다는 작은 수가 나오는데 두 값을 곱하게 되면 long long을 벗어나지 않는다. 다만, 나머지 연산에서 세 번의 곱을 연산을 한다면 문제가 생긴다. 구조가 int * int * int가 되기 때문에 오버플로우가 발생할 수밖에 없다  

 

틀린코드는

return ((tmp % c) * (tmp % c) * (a % c)) % c;

바른코드는

return ((((tmp % c) * (tmp % c)) % c) * a) % c;