「NOI 2018」屠龙勇士

Problem

Description

小 D 最近在网上发现了一款小游戏。游戏的规则如下:

  • 游戏的目标是按照编号 1\sim n 顺序杀掉 n 条巨龙,每条巨龙拥有一个初始的生命值 a_i 。同时每条巨龙拥有恢复能力。当其使用恢复能力时,它的生命值就会每次增加 p_i ,直至生命值非负。只有在攻击结束后且当生命值恰好 0 时它才会死去。
  • 游戏开始时玩家拥有 m 把攻击力已知的剑,每次面对巨龙时,玩家只能选择一把剑,当杀死巨龙后这把剑就会消失,但作为奖励,玩家会获得全新的一把剑。

小 D 觉得这款游戏十分无聊,但最快通关的玩家可以获得 ION2018 的参赛资格,于是小 D 决定写一个笨笨的机器人帮她通关这款游戏,她写的机器人遵循以下规则:

  • 每次面对巨龙时,机器人会选择当前拥有的,攻击力不高于巨龙初始生命值中攻击力最大的一把剑作为武器。如果没有这样的剑,则选择攻击力最低的一把剑作为武器。
  • 机器人面对每条巨龙,它都会使用上一步中选择的剑攻击巨龙固定的 x 次,使巨龙的生命值减少 x \times ATK
  • 之后,巨龙会不断使用恢复能力,每次恢复 p_i 生命值。若在使用恢复能力前或某一次恢复后其生命值为 0 ,则巨龙死亡,玩家通过本关。

那么显然机器人的攻击次数是决定能否最快通关这款游戏的关键。小 D 现在得知了每条巨龙的所有属性,她想考考你,你知道应该将机器人的攻击次数 x 设置为多少,才能用最少的攻击次数通关游戏吗?
当然如果无论设置成多少都无法通关游戏,输出 -1 即可。

Constraints

1\le n,m\le 10^{5},1\le a_{i}\le 10^{12},1\le ATK_{i}\le 10^{6}

Solution

Analysis

显然可得到如下两个关系式:

\forall i\in[1, n]:x\times atk_{i}\equiv a_{i}\pmod{p_{i}}

x\ge\max_{i=1}^{n}\left\lfloor\frac{a_{i}+atk_{i}-1}{atk_{i}}\right\rfloor

考虑第一个柿子,显然是个 EXCRT 的形式,但是左边的 atk_{i} 不好处理,考虑 EXCRT 的推导过程。

设前 i-1 个方程的通解为 x+k\times lcm\left(k\in\mathbb{Z}\right) ,有:

\left(x+k\times lcm\right)\times atk_{i}\equiv a_{i}\pmod{p_{i}}

k\times lcm\times atk_{i}+t\times p_{i}=a_{i}-x\times atk_{i}

\text{exgcd} 求出最小的合法 k 并修改通解即可。

考虑第二个柿子,则求出所有 n 个方程的通解 x+k\times lcm\left(k\in\mathbb{Z}\right) 后,找到满足

x+k\times lcm\ge\max_{i=1}^{n}\left\lfloor\frac{a_{i}+atk_{i}-1}{atk_{i}}\right\rfloor

的最小 k x+k\times lcm 即为答案。

时间复杂度 O\left(Tn\log n\right)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include<set>
#include<cstdio>
#include<algorithm>

using i64=long long;
using uchar=unsigned char;

constexpr int maxn(100000);

template<typename _Tp>
inline void chkMax(_Tp&x,const _Tp&y)
{(x<y)&&(x=y);}

namespace IOManager{
constexpr int FILESZ(131072);
char buf[FILESZ];
const char*ibuf=buf,*tbuf=buf;

struct IOManager{
inline char gc()
{return(ibuf==tbuf)&&(tbuf=(ibuf=buf)+fread(buf,1,FILESZ,stdin),ibuf==tbuf)?EOF:*ibuf++;}

template<typename _Tp>
inline operator _Tp(){
_Tp s=0u;char c=gc();
for(;c<48;c=gc());
for(;c>47;c=gc())
s=(_Tp)(s*10u+c-48u);
return s;
}
};
}IOManager::IOManager io;

template<typename _Tp,class x_tp>
inline void exgcd(const _Tp&x,const _Tp&y,_Tp&d,x_tp&a,x_tp&b){
if(y)exgcd(y,x%y,d,b,a),b-=x/y*a;
else a=1,b=0,d=x;
}
inline i64 mul(const i64&x,const i64&y,const i64&p)
{return(x*y-(i64)(((long double)x*y+0.5)/p)*p)%p;}

inline std::pair<i64,i64>EXCRT(const int&n,const i64*const&a,const i64*const&p,const i64*const&atk){
i64 ans=0,lcmp=1,d,tx,ty,t;
for(int i=1;i<=n;++i){
exgcd(lcmp*atk[i],(i64)p[i],d,tx,ty);
t=((a[i]-ans*atk[i])%p[i]+p[i])%p[i];
if(t%d)
return std::make_pair(-1,-1);

ans+=mul(tx,t/d,p[i]/d)*lcmp;
lcmp*=p[i]/d;
ans=(ans%lcmp+lcmp)%lcmp;
}return std::make_pair((ans+lcmp)%lcmp,lcmp);
}

i64 a[maxn+1],p[maxn+1],atk[maxn+1],pri[maxn+1];

std::multiset<i64>s;

int main(){
for(int T=io;T;){
const int n=io;int m=io;
for(int i=1;i<=n;++i)
a[i]=io;
for(int i=1;i<=n;++i)
p[i]=io;
for(int i=1;i<=n;++i)
pri[i]=io;
for(;m;--m)
s.insert((int)io);

for(int i=1;i<=n;s.insert(pri[i++])){
auto it=s.upper_bound(a[i]);
if(it==s.begin())
atk[i]=*it,
s.erase(it);
else
atk[i]=*--it,
s.erase(it);
}

i64 mx=0;
for(int i=1;i<=n;++i)
chkMax(mx,(a[i]+atk[i]-1)/atk[i]);

auto ans=EXCRT(n,a,p,atk);
if(~ans.first)
for(;ans.first<mx;)
ans.first+=ans.second;
printf("%lld\n",ans.first);

if(--T)
s.clear();
}

return 0;
}