题目链接
https://www.luogu.com.cn/problem/P4774
题解
首先，根据题意，我们可以很容易预处理出面对第 \(i\) 条龙时使用的剑，记其伤害值为 \(c_i\)。
做完了这样一步预处理过后，会发现我们实际上要解若干个形如 \(c_ix\equiv a_i \pmod{p_i}\) 这样的同余方程组联立后的最小解。
解这样的方程组，第一个前提条件是 \(a_i \leq p_i\)，如果不满足这个条件的话，可能会出现龙的血量在 \(\bmod\ p_i\) 意义下为零，但实际血量不为零的问题。
不过好在不满足 \(a_i \leq p_i\) 的测试数据都满足 \(p_i=1\)，这意味着这种情况下的答案将直接为 \(\max \left \lceil \frac{a_i}{c_i} \right \rceil\)。
排除这种情况后，我们下面的讨论均在 \(a_i \leq p_i\) 的前提下进行。
这个方程组看起来像是可以应用扩展中国剩余定理（ExCRT）的样子。但是 ExCRT 要求 \(x\) 前面的系数必须为 \(1\)。
将方程组两边同时除 \(c_i\)？不行，模 \(p_i\) 意义下 \(c_i\) 的逆元不一定存在。
考虑将线性同余方程改写成不定方程的形式。
像 \(c_ix\equiv a_i \pmod{p_i}\) 就可以改写为：\(c_ix+p_iy=a_i\)。
接下来用扩展欧几里得算法来解这个方程组即可。
等等！扩展欧几里得算法解的是形如 \(ax+by=\gcd(a,b)\) 形式的不定方程，上面的方程显然不满足这个形式，不能直接用 exgcd 来解。
换个元后稍微推一下：
我们设 \(x=\frac{a_i}{\gcd(c_i,p_i)}x’\)，\(y=\frac{a_i}{\gcd(c_i,p_i)}y’\)。
则原来的方程可以改写为：
$$
c_ix’+p_iy’=\gcd(c_i,p_i)
$$
现在方程变成了标准形式，可以直接解了。
设上面方程的一组解是 \(x’=x’_0\)，\(y’=y’_0\)，则原方程与之对应的解为 \(x_0=\frac{a_i}{\gcd(c_i,p_i)}x’_0\)，\(y_0=\frac{a_i}{\gcd(c_i,p_i)}y’_0\)。
这是一个方程组的解，对于多个方程组，我们需要用 ExCRT（本质上还是扩展欧几里得）来合并它们。
简单来说，对于两个线性同余方程：
$$
\begin{cases}
x \equiv a_1 \pmod {p_1}\\
x \equiv a_2 \pmod {p_2}\\
\end{cases}
$$
我们还是把它们改写成不定方程的形式：
$$
\begin{cases}
x = a_1 +p_1y_1\\
x = a_2 +p_2y_2\\
\end{cases}
$$
联立后消去 \(x\)，用扩展欧几里得解 \(y_1,y_2\) 即可合并两个方程。
#include <iostream>
#include <set>
#include <algorithm>
using namespace std;
long long a[100005],p[100005];
long long nswd[100005],c[100005];
multiset<long long> swd;
int n,m;
long long exgcd(long long a,long long b,long long&x,long long&y)
{
if(b==0)
{
x=1,y=0;
return a;
}
long long g=exgcd(b,a%b,x,y);
int t=x;
x=y;
y=t-a/b*y;
return g;
}
long long mul(long long x,long long y,long long p)
{
long long ans=0;
while(y)
{
if(y&1)ans=(ans+x)%p;
x=(x+x)%p;
y>>=1;
}
return ans;
}
namespace sub1//p_i maybe greater than a_i, but guaranteed p_i=1
{
bool check()
{
bool flag=true;
for(int i=1;i<=n;i++)
flag&=(p[i]==1);
return flag;
}
void solve()
{
long long ans=0;
for(int i=1;i<=n;i++)
ans=max(ans,(long long)((a[i]/c[i])+(a[i]%c[i]!=0)));
cout<<ans<<endl;
}
}
int main()
{
ios::sync_with_stdio(false);
int t;
cin>>t;
while(t--)
{
bool flag=true;
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n;i++)
cin>>p[i];
for(int i=1;i<=n;i++)
cin>>nswd[i];
swd.clear();
for(int i=1;i<=m;i++)
{
long long x;
cin>>x;
swd.insert(x);
}
for(int i=1;i<=n;i++)
{
auto it=swd.upper_bound(a[i]);
if(it!=swd.begin())it--;
c[i]=*it;
swd.erase(it);
swd.insert(nswd[i]);
}
long long ans=0,z=1;
if(sub1::check())
{
sub1::solve();
continue;
}
for(int i=1;i<=n;i++)
{
c[i]%=p[i],a[i]%=p[i];
if(!c[i]&&a[i])
{
cout<<-1<<endl;
flag=false;break;
}
if(!c[i]&&!a[i])continue;
long long x,y;
long long g=exgcd(c[i],p[i],x,y);
if(a[i]%g)
{
cout<<-1<<endl;
flag=false;break;
}
p[i]/=g;
a[i]=mul(a[i]/g,(x%p[i]+p[i])%p[i],p[i]);
g=exgcd(z,p[i],x,y);
if((a[i]-ans)%g)
{
cout<<-1<<endl;
flag=false;break;
}
z=z/g*p[i];
ans=(ans+mul(mul(z/p[i],((a[i]-ans)%z+z)%z,z),(x%z+z)%z,z))%z;
}
if(flag)cout<<ans<<endl;
}
return 0;
}