[BOJ] 13172 Σ

https://www.acmicpc.net/problem/13172

13172번: Σ

알고리즘: 분할정복(제곱)

---

 

$\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) + a_2 \times b_2^{-1}\ \left(mod\ X\right)$ 이 성립한다.

 

분할정복을 이용하여 X-2제곱(=10^9 + 5)을 구해주고 각각을 다 더해주면 AC.