洛谷4774 [NOI2018]屠龙勇士

题意

解同余方程组：

$$x\times ATK_i\equiv A_i\pmod {P_i}\tag{1}$$

$ATK$ 还需要平衡树或者multiset推出来。

其中方程个数 $N\le 10^{5}$ ，$A_i\le 10^{12}$ 。

题解

将原式化简：

$$ATK_i\times x+P_i\times y=A_i$$

可以用 $\text{exgcd}$ 求出 $x$ 的最小整数解 $S_x$，并用一般解公式得到下面的同余方程：

$$x\equiv S_x \pmod {\dfrac{P_i}{\text{gcd}(ATK_i,P_i)}}\tag{2}$$

然后用 $\text{excrt}$ 求解就行了。

但针对这道题而言，如果 $A_i > P_i$ ，那方程 $(1)$ 就求不出解了，所以需要特判。

仔细看下表格，发现有可能出现 $A_i > P_i$ 的数据点都满足 $P_i=1$ 。这种情况答案就很显然是 $\max_{i=1}^n \lceil \dfrac{A_i}{ATK_i} \rceil$ 。

还有题目很显然会爆long long，我又不会写龟速乘，所以拿__int128水过了。

#include<bits/stdc++.h>
#define ll __int128

using namespace std;

inline ll read()
{
    char ch=getchar();
    ll f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

multiset <ll> s;
ll t,n,m,M,hp[100005],p[100005],nxt[100005],atk[100005];

ll exgcd(ll l,ll r,ll &x,ll &y)
{
    if (r==0)
    {
        x=1; y=0;
        return l;
    }
    ll ans=exgcd(r,l%r,y,x);
    y-=l/r*x;
    return ans;
}

inline ll excrt()
{
    ll A=0; M=1;
    for (ll i=1;i<=n;i++)
    {
        ll a=atk[i],b=p[i],c=hp[i],x=0,y=0;
        ll g=exgcd(a,b,x,y);
        if (c%g) return -1;
        b/=g; c/=g;
        x=((x*c)%b+b)%b;
        ll ai=x,mi=b; //得到方程(2)
        a=M,b=mi,c=ai-A,x=0,y=0;
        g=exgcd(a,b,x,y);
        if (c%g) return -1;
        b/=g; c/=g;
        x=((x*c)%b+b)%b;
        A+=x*M;
        M=M*mi/g;
        A%=M;
    }
    return A;
}

void print(ll x)
{
    if (x==-1) return (void)printf("-1");
    if (x==0) return;
    print(x/10);
    putchar(x%10+'0');
}

signed main()
{
    t=read();
    while (t--)
    {
        s.clear();
        n=read(); m=read();
        for (ll i=1;i<=n;i++) hp[i]=read();
        bool pe1=1;
        for (ll i=1;i<=n;i++) p[i]=read(),pe1&=(p[i]==1);
        for (ll i=1;i<=n;i++) nxt[i]=read();
        for (ll i=1;i<=m;i++) s.insert(read());
        ll mx=0;
        for (ll i=1;i<=n;i++)
        {
            multiset<ll>::iterator it=s.upper_bound(hp[i]);
            if (it!=s.begin()) it--;
            atk[i]=*it;
            s.erase(it); s.insert(nxt[i]);
            mx=max(mx,(hp[i]+atk[i]-1)/atk[i]);
        }
        if (pe1) print(mx); //pi=1
        else print(excrt());
        puts("");
    }
    return 0;
}