[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 ;
 }