황소개발자

나머지 모듈 연산에 대하여 : 오버플로우 방지 [+ * - /] 본문

백준 문제 풀이

나머지 모듈 연산에 대하여 : 오버플로우 방지 [+ * - /]

hjp845 2020. 2. 27. 15:40
반응형

(a + b) % c 

는

(a % c + b % c) % c

와 같으며

곱셈연산에 있어서도 성립한다.

나누기 연산은

(a / b) % c

는

(a * b ^ (c - 2)) % c    --- a와 b는 서로소, c는 소수 (페르마의 소정리)

와 같으며

빼기 연산은

(a - b) % c

는

(a % c - b % c + c) % c

와 같다

알고리즘문제에 있어

모듈(나머지) 연산은 오버플로우 방지에 필수다.

반응형
저작자표시 비영리

'백준 문제 풀이' 카테고리의 다른 글

백준 9095 파이썬 python : 1, 2, 3 더하기 @@황소처럼 우직하게@@ 숏코딩  (0) 2020.02.28
백준 1476 파이썬 python : 날짜 계산 @@황소처럼 우직하게@@ 어렵게 생각하지 마세요  (0) 2020.02.27
백준 2309 파이썬 python : 일곱 난쟁이 @@황소처럼 우직하게@@ 최적화를 고려하세요  (0) 2020.02.27
파이썬에서 삼항연산자는 이렇게 사용하자  (0) 2020.02.27
백준 6588 파이썬 python : 골드바흐의 추측 @@황소처럼 우직하게@@ 에레토스테네스의 체 + 최적화  (0) 2020.02.27
'백준 문제 풀이' Related Articles more
Comments