点此看题
这个姐姐博客写的好好，我爱了：https://www.luogu.com.cn/blog/emptyset/solution-p4774
其实这道题就是考察你会不会推 e x c r t \tt excrt excrt，原题就是让你解这个式子： x × b i = a i m o d p x\times b_i=a_i\mod p x×bi=aimodp假设我们得到了前 i i i项的解记为 R R R，以前的模数 l c m \tt lcm lcm是 M M M， b i ( R + M x ) = a i m o d p b_i(R+Mx)=a_i\mod p bi(R+Mx)=aimodp，转化成二元一次方程： b i M x + p y = a i − R b i b_iMx+py=a_i-Rb_i biMx+py=ai−Rbi，这类式子一看就是老扩欧了，解出来就好了。
然后这道题我竟然跑到了某谷 r a n k 1 \tt rank1 rank1，我的常数好小啊（惊讶）
#include <cstdio> #include <set> using namespace std; #define int long long const int M = 100005; int read() { int num=0,flag=1;char c; while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1; while(c>='0'&&c<='9')num=(num<<3)+(num<<1)+(c^48),c=getchar(); return num*flag; } int T,n,m,mx,a[M],b[M],t[M],p[M]; multiset<int> s; int exgcd(int a,int b,int &x,int &y) { if(!b) { x=1;y=0; return a; } int d=exgcd(b,a%b,y,x); y-=x*(a/b); return d; } int crt() { int R=0,M=1,x,y; for(int i=1;i<=n;i++) { //printf("%lld %lld %lld\n",a[i],b[i],p[i]); int d=exgcd((__int128)b[i]*M%p[i],p[i],x,y); if((a[i]-b[i]*R)%d) return -1; x=(x%p[i]+p[i])%p[i]; R=(R+(__int128)(a[i]-b[i]*R)/d*x%p[i]*M)%(M*=(p[i]/d)); } R=(R+M)%M; if(R<mx) R+=((mx-R-1)/M+1)*M; return R; } signed main() { T=read(); while(T--) { n=read();m=read();s.clear();mx=0; for(int i=1;i<=n;i++) a[i]=read(); for(int i=1;i<=n;i++) p[i]=read(); for(int i=1;i<=n;i++) t[i]=read(); for(int i=1;i<=m;i++) s.insert(read()); for(int i=1;i<=n;i++) { multiset<int>::iterator it=s.upper_bound(a[i]); if(it!=s.begin()) it--; b[i]=*it;s.erase(it);s.insert(t[i]); mx=max(mx,(a[i]-1)/b[i]+1); } printf("%lld\n",crt()); } }