[NOI2018]屠龙勇士(exCRT)

首先很明显剑的选择是唯一的，直接用multiset即可。

　　接下来可以发现每条龙都是一个模线性方程。设攻击第i条龙的剑的攻击力为$s_i$，则$s_ix\equiv a_i\ (mod\ p_i)$。

　　现在需要将方程化成$x\equiv c_i\ (mod\ m_i)$的形式，从而使用exCRT解决。

　　变式：$s_ix+p_iy=a_i$，先同除以$gcd(s_i,p_i)$，再使用exgcd解不定方程，求x的最小正整数解。

　　注意判无解，exCRT结束之后注意要使$x\geqslant max(\frac{a_i}{s_i})$

 #include<set>

 #include<cstdio>

 #include<algorithm>

 #define rep(i,l,r) for (int i=(l); i<=(r); i++)

 typedef long long ll;

 using namespace std;

 const int N=;

 multiset<ll>S;

 bool mark;

 int n,k,T;

 ll mx,a[N],p[N],more[N],s[N],c[N],m[N];

 ll gcd(ll a,ll b){ return b ? gcd(b,a%b) : a; }

 ll mul(ll a,ll b,ll mod){

     ll res=; a%=mod; b%=mod;

     for (; b; a=(a<<)%mod,b>>=)

         if (b & ) res=(res+a)%mod;

     return res;

 }

 void exgcd(ll a,ll b,ll &x,ll &y){

     if (!b){ x=; y=; return; }

     exgcd(b,a%b,y,x); y-=(a/b)*x;

 }

 ll inv(ll a,ll b){ ll x,y; exgcd(a,b,x,y); x=(x%b+b)%b; return x; }

 bool merge(ll c1,ll c2,ll m1,ll m2,ll &c3,ll &m3){

     ll d=gcd(m1,m2); m3=m1/d*m2;

     if (c2<c1) swap(c1,c2),swap(m1,m2);

     if ((c2-c1)%d) return ;

     c3=(mul(mul(inv(m1/d,m2/d),(c2-c1)/d,m2/d),m1,m3)+c1)%m3;

     return ;

 }

 void work(){

     scanf("%d%d",&n,&k); mark=; mx=; S.clear();

     rep(i,,n) scanf("%lld",&a[i]);

     rep(i,,n) scanf("%lld",&p[i]);

     rep(i,,n) scanf("%lld",&more[i]);

     rep(i,,k) scanf("%lld",&s[i]),S.insert(s[i]);

     rep(i,,n){

         multiset<ll>::iterator it=S.upper_bound(a[i]);

         if (it!=S.begin()) it--;

         ll s=*it; S.erase(it); S.insert(more[i]);

         mx=max(mx,(a[i]-)/s+);

         ll d=gcd(s,p[i]);

         if (a[i]%d) { mark=; break; }

         m[i]=p[i]/d; c[i]=mul(inv(s/d,m[i]),a[i]/d,m[i]);

     }

     if (!mark) { puts("-1"); return; }

     rep(i,,n) if (!merge(c[i-],c[i],m[i-],m[i],c[i],m[i])) { mark=; break; }

     if (!mark) { puts("-1"); return; }

     if (c[n]<mx) c[n]+=((mx-c[n]-)/m[n]+)*m[n];

     printf("%lld\n",c[n]);

 }

 int main(){

     freopen("dragon.in","r",stdin);

     freopen("dragon.out","w",stdout);

     for (scanf("%d",&T); T--; ) work();

     return ;

 }