传送门
前言
我是唐诗，考场没开这题。导致看都没看，直接考试策略大失误。其实知道了这题是个扩展中国剩余定理之后就很好做了。
题意
非常奇妙。
小 D 最近在网上发现了一款小游戏。游戏的规则如下：
- 游戏的目标是按照编号 \(1 \rightarrow n\) 顺序杀掉 \(n\) 条巨龙，每条巨龙拥有一个初始的生命值 \(a_i\) 。同时每条巨龙拥有恢复能力，当其使用恢复能力时，它的生命值就会每次增加 \(p_i\) ，直至生命值非负。只有在攻击结束后且当生命值 恰好 为 \(0\) 时它才会死去。
- 游戏开始时玩家拥有 \(m\) 把攻击力已知的剑，每次面对巨龙时，玩家只能选择一把剑，当杀死巨龙后这把剑就会消失，但作为奖励，玩家会获得全新的一把剑。
小 D 觉得这款游戏十分无聊，但最快通关的玩家可以获得 ION2018 的参赛资格，于是小 D 决定写一个笨笨的机器人帮她通关这款游戏，她写的机器人遵循以下规则：
- 每次面对巨龙时，机器人会选择当前拥有的，攻击力不高于巨龙初始生命值中攻击力最大的一把剑作为武器。如果没有这样的剑，则选择 攻击力最低 的一把剑作为武器。
- 机器人面对每条巨龙，它都会使用上一步中选择的剑攻击巨龙固定的 \(x\) 次，使巨龙的生命值减少 \(x \times ATK\) 。
- 之后，巨龙会不断使用恢复能力，每次恢复 \(p_i\) 生命值。若在使用恢复能力前或某一次恢复后其生命值为 \(0\) ，则巨龙死亡，玩家通过本关。
那么显然机器人的攻击次数是决定能否最快通关这款游戏的关键。小 D 现在得知了每条巨龙的所有属性，她想考考你，你知道应该将机器人的攻击次数 \(x\) 设置为多少，才能用最少的攻击次数通关游戏吗？
当然如果无论设置成多少都无法通关游戏，输出 \(-1\) 即可。
思路
part 1
首先，我们很容易能够知道。其实每一只龙 \(i\) 一定有对应的用来砍它的剑。为什么，这里简单证明一下。第一步，注意题目中说的：
每次面对巨龙时，机器人会选择当前拥有的，攻击力不高于巨龙初始生命值中攻击力最大的一把剑作为武器。如果没有这样的剑，则选择 攻击力最低 的一把剑作为武器。
这就说明，每一次选剑的策略是一定的，那么每一只龙就一定有一把对应用来砍它的剑 \(b_i\)。即使后面加入新的剑也是有同样的。相当于我们可以收先处理出每一只龙所对应的剑。这里的实现必须是 \(O(n \log n)\) 的。考虑使用平衡树或者直接使用 multiset。显然 multiset 会好写一些。
这一部分的处理代码就长这样（其中 s 就是 multiset）：
for(int i=1;i<=n;i++){
auto place=s.upper_bound(a[i]);
if(place!=s.begin()){
place--;
}
b[i]=*place;
s.erase(place);
s.insert(t[i]);
maxn=max(maxn,(a[i]-1)/b[i]+1);
}
part 2
然后我们进入核心阶段。由于上面我们找到了每一只龙对应的剑 \(b_i\) 且我们知道 我们要固定攻击 \(k\) 次。那么就有我们造成的总伤害为 \(b_i \times k\)。又因为龙的初始生命值为 \(a_i\)。那么易得满足让这一只龙去世的满足条件的 \(x\) 也一定满足下面这个式子：
\[b_i \times x \equiv a_i \pmod {q_i} \]那么多条龙也是一样的，我们就可以列出方程组：
\[\left\{ \begin{array}{l} \text{$b_1 \times x \equiv a_1 \pmod {q_1}$} \\ \text{$b_2 \times x \equiv a_2 \pmod {q_2}$} \\ \text{......} \\ \text{$b_n \times x \equiv a_n \pmod {q_n}$} \end{array} \right. \]part 3
现在已经能看出来，这题明显可以用 ExCrt 求解。但是这里还有个系数 \(b_i\)。应该怎么办。其实比较好处理。这里笔者参考了 emptysetvvvv 大佬的 博客。这篇文章大致是这样说的：我们先假设我们已经得到了前 \(i - 1\) 个方程的解，记为 \(res\)，且假设有 LCM 等于 \(\mathrm{lcm}(p_1,p_2 ...... p_{i-1})\)。对于前 \(i\) 个方程，我们想得到它们的解就是想找到一个 \(x\) 满足下面这式子：
\[b_i \times (res + LCM \times x) \equiv a_i \pmod {q_i} \]为什么？首先我们可以知道 \(LCM \times x + res\) 为前 \(i-1\) 的通解。那么上面这个式子就很显然了。
然后，我们把上面那个式子移项。就能发现这个式子其实就等价于：
\[(b_i \times LCM) \times x + p_i \times y = a_i - b_i \times ans \]于是直接扩展欧几里得求解。注意计算过程会爆 long long。建议直接使用 __int128。
AC code
#include<bits/stdc++.h>
#define int __int128
using namespace std;
namespace WYL{
const int N=1e5+10;
multiset<int> s;
int T,n,m,a[N],b[N],p[N],t[N],maxn=0;
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0' && ch<='9')
x=x*10+ch-'0',ch=getchar();
return x*f;
}
inline void Write(int x){
if(x<0)
putchar('-'),x=-x;
if(x>9)
Write(x/10);
putchar(x%10+'0');
return;
}
int gsc(int a,int b,int mod){
int ans=0;
while(b){
if(b&1){
ans=(ans+a)%mod;
}
a=(a+a)%mod;
b/=2;
}
return ans;
}
void exgcd(int a,int b,int &x,int &y,int &gcd) {
if(!b){
x=1;
y=0;
gcd=a;
}else{
exgcd(b,a%b,y,x,gcd);
y-=(a/b)*x;
}
return;
}
int solve(){
int ans=0,lcm=1,x,y,Gcd,yi,er,san;
for(int i=1;i<=n;i++){
// yi=gsc(b[i],lcm,p[i]);
yi=b[i]*lcm%p[i];
// cout<<"pass1"<<endl;
er=p[i];
san=(a[i]-b[i]*ans%p[i]+p[i])%p[i];
// cout<<"pass2"<<endl;
exgcd(yi,er,x,y,Gcd);
// cout<<"pass3"<<endl;
x=(x%er+er)%er;
if(san%Gcd){
return -1;
}
// lcm=lcm*(er/Gcd);
ans=(ans+(san/Gcd)*x%(er/Gcd)*lcm%(lcm*=er/Gcd))%lcm;
// ans=(ans+gsc(san/Gcd,x,er/Gcd)*lcm%(lcm*er/Gcd))%lcm;
}
if(ans<maxn){
ans=ans+((maxn-ans-1)/lcm+1)*lcm;
}
return ans;
}
int main(){
T=read();
while(T--){
s.clear();
n=read();
m=read();
maxn=0;
for(int i=1;i<=n;i++){
a[i]=read();
}
for(int i=1;i<=n;i++){
p[i]=read();
}
for(int i=1;i<=n;i++){
t[i]=read();
}
for(int i=1;i<=m;i++){
int opt;
opt=read();
s.insert(opt);
}
// cout<<"pass"<<endl;
for(int i=1;i<=n;i++){
auto place=s.upper_bound(a[i]);
if(place!=s.begin()){
place--;
}
b[i]=*place;
s.erase(place);
s.insert(t[i]);
maxn=max(maxn,(a[i]-1)/b[i]+1);
}
// cout<<ExCRT()<<endl;
Write(solve());
puts("");
}
return 0;
}
}
signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
// freopen("dragon.in","r",stdin);
// freopen("dragon.out","w",stdout);
WYL::main();
return 0;
}