1629 분할정복1 [C++] 모듈러 사칙 연산 (BOJ 1629: 곱셈) 백준 1629: 곱셈 문제를 풀다가 자꾸 시간초과가 나오다보니 결국 하는 방법을 찾게 되었는데 모듈러 계산에 대해서 공부할 필요성을 느끼게 되었다. 앞으로 모듈러 연산이 나올 때마다 여기다가 다시 정리를 해야겠다. 모듈러 사칙 연산 덧셈, 뺄셈, 곱셈에 대해서는 다음 식이 항상 성립한다. (이부분에서는 mod M을 % M이라고 표현) 덧셈 : (a+b) % M = ((a % M) + (b % M)) % M 뺄셈 : (a-b) % M = ((a%M) - (a%M)) % M 곱셈 : (a*b) % M = ((a%M) * (b%M)) % M 나눗셈 : 모듈로 연산에서 나눗셈은 곱셈 역원(multiplicative inverse)을 곱하는 방식으로 이루어진다. 모듈로 곱셈 역원은 항상 존재하는 것이 아니라, b.. 2023. 9. 15. 이전 1 다음