exponentiation_by_squaring
-
[BOJ] 13172 ΣPS/BOJ 2022. 7. 18. 22:12
https://www.acmicpc.net/problem/13172 13172번: Σ 모듈러가 11에서 1,000,000,007이 되어 답이 달라졌지만, 역시 3을 곱한 다음 1,000,000,007으로 나눈 나머지는 7이 된다. www.acmicpc.net 알고리즘: 분할정복(제곱) $\frac{S_1}{N_1}+\frac{S_2}{N_2}에서,\\$ $\frac{S_1}{N_1}: a_1 \times b_1^{-1}\ \left(mod\ X\right)\\$ $\frac{S_2}{N_2}: a_2 \times b_2^{-1}\ \left(mod\ X\right)\\$ $\frac{S_1}{N_1}+\frac{S_2}{N_2} : a_1 \times b_1^{-1}\ \left(mod\ X\right)..