| 1 | #include "egcd.cpp" |
| 2 | ll crt(vector<ll> &as, vector<ll> &ns) { |
| 3 | ll cnt = size(as), N = 1, x = 0, r, s, l; |
| 4 | rep(i,0,cnt) N *= ns[i]; |
| 5 | rep(i,0,cnt) egcd(ns[i], l = N/ns[i], r, s), x += as[i]*s*l; |
| 6 | return smod(x, N); } |
| 7 | pair<ll,ll> gcrt(vector<ll> &as, vector<ll> &ns) { |
| 8 | map<ll,pair<ll,ll> > ms; |
| 9 | rep(at,0,size(as)) { |