(int n)
| 27 | |
| 28 | // 中国剩余定理模版 |
| 29 | public static long crt(int n) { |
| 30 | long lcm = 1; |
| 31 | for (int i = 1; i <= n; i++) { |
| 32 | lcm = lcm * m[i]; |
| 33 | } |
| 34 | long ai, ci, ans = 0; |
| 35 | for (int i = 1; i <= n; i++) { |
| 36 | // ai = lcm / m[i] |
| 37 | ai = lcm / m[i]; |
| 38 | // ai逆元，在%m[i]意义下的逆元 |
| 39 | exgcd(ai, m[i]); |
| 40 | // ci = (ri * ai * ai逆元) % lcm |
| 41 | ci = multiply(r[i], multiply(ai, x, lcm), lcm); |
| 42 | ans = (ans + ci) % lcm; |
| 43 | } |
| 44 | return ans; |
| 45 | } |
| 46 | |
| 47 | // 讲解139 - 扩展欧几里得算法 |
| 48 | public static long d, x, y, px, py; |