题解
考虑增量法。
假设我们已经做完了前k个条件，前面的模数连乘起来的结果为M，答案为X，当前的攻击力为x，龙的血量为a。
那么我们这一次的答案的表达形式是X+t*M的。
这一次需要满足的是x(X+t*M)≡a(%p).
只有t一个未知量，用exgcd就可以解了。
然后就是恶心的特判了。。。
代码
#include<iostream> #include<cstdio> #include<set> #include<cmath> #define N 100002 using namespace std; typedef long long ll; ll x,y,p[N],a[N],b[N],M,X,n,m,tag,t; multiset<ll>s; multiset<ll>::iterator it; inline ll rd(){ ll x=0;char c=getchar();bool f=0; while(!isdigit(c)){if(c=='-')f=1;c=getchar();} while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();} return f?-x:x; } inline ll power(ll x,ll y,ll mod){ x=(x%mod+mod)%mod;y=(y%mod+mod)%mod; ll ans=0; while(y){ if(y&1)(ans+=x)%=mod; (x<<=1)%=mod; y>>=1; } return ans; } void exgcd(ll a,ll b){ if(!b){x=1;y=0;return;} exgcd(b,a%b); ll k=x;x=y;y=k-a/b*y; } ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} inline void EXCRT(ll a,ll b,ll c){ ll aa=x*M,bb=c,cc=b-a*X; ll g=gcd(aa,bb); if(cc%g){tag=1;return;} if(c==1){ bb/=g; ll p=M;M*=bb; X+=max(0ll,(ll)ceil((double)((double)b/a-X)/p))*p; return; } aa/=g;bb/=g;cc/=g; exgcd(aa,bb); x=power(x,cc,bb); ll p=M;M*=bb; x=power(x,p,M); X=(X+x)%M; } int main(){ // freopen("1.in","r",stdin); t=rd(); while(t--){ n=rd();m=rd();tag=0;s.clear();M=1;X=0; for(int i=1;i<=n;++i)a[i]=rd(); for(int i=1;i<=n;++i)p[i]=rd(); for(int i=1;i<=n;++i)b[i]=rd(); for(int i=1;i<=m;++i)x=rd(),s.insert(x); for(int i=1;i<=n;++i){ it=s.upper_bound(a[i]);if(it!=s.begin())--it; x=*it;s.erase(it); EXCRT(x,a[i],p[i]); if(tag)break; s.insert(b[i]); } if(tag)printf("-1 "); else cout<<X<<endl; } return 0; }