洛谷题目链接:[NOI2018]屠龙勇士
因为markdown复制过来有点炸格式,所以看题目请戳上面.
题解: 因为杀死一条龙的条件是在攻击(x)次,龙恢复(y)次血量((yin N^{*}))后龙的血量恰好为(0).那么根据题意我们可以列出方程:
[atk_i*xequiv hp_i(mod p_i)
]
这个形式是不是很像中国剩余定理的形式:(xequiv b_i(mod a_i)).
事实上我们可以直接将这个方程看做一个同余方程,即$$atk_ix+p_iy = hp_i$$
那么这个式子就代表着攻击了(x)次,恢复了(-y)次血量,因为解出来的(x)和(y)一定是一正一负的.这样求解的话,我们就需要考虑(y)的定义域了.但是事实上不用每次都用最小合法解,只需要每次找到一个解,最后求出整个方程组的解的时候将解构造成合法的形式.因为每次攻击龙都会解出来一个解(x_i),最后求出来的解只要保证(ans>=max{x_i})就一定是合法的了.
这样的话,合并上面这个式子就只剩下中国剩余定理的部分了.设(lcm=lcm{p_i},iin[1,k-1]),(x_0)为前(k-1)个同余方程的解,那么(x_0+t*lcm)也一定是前(k-1)个方程的解,为了满足第(k)个式子,那么我们需要找到一个(t)使得$$(x_0+tlcm)atk_iequiv hp_i(mod p_i)$$
[lcm*atk_i*t+p_i*y = hp_i-atk_i*x_0
]
设(a=lcm*atk_i,b=p_i,c=hp_i-atk_i*x_0,x=t),则有(a*x+b*y=c),也就是同余方程的标准形式.
我们应该如何判断无解呢?对于这样的不定方程,有解的条件为(gcd(a,b)|c),在做(exgcd)的时候判断一下就可以了.
那么每求出(t)的一个解,就可以得到前(k)个同余方程的解(x_0+t*lcm),做完之后再更新一下(lcm=lcm(lcm, p_i))就可以了.
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
const int inf = 0x3f3f3f3f;
typedef int _int;
#define int long long
int T, n, m, hp[N], p[N], rew[N], cnt = 0, root, r1, r2, r3, ans = 0, mx;
struct treap{
int ch[2], val, rd, size;
treap(){ ch[0] = ch[1] = val = rd = size = 0; }
}t[N*2];
int newnode(int val){
t[++cnt].val = val, t[cnt].rd = rand(), t[cnt].size = 1;
return cnt;
}
void up(int x){ t[x].size = t[t[x].ch[0]].size+t[t[x].ch[1]].size+1; }
void split(int x, int val, int &a, int &b){
if(!x){ a = b = 0; return; }
if(t[x].val <= val) a = x, split(t[x].ch[1], val, t[x].ch[1], b);
else b = x, split(t[x].ch[0], val, a, t[x].ch[0]); up(x);
}
int merge(int x, int y){
if(!x || !y) return x+y;
if(t[x].rd < t[y].rd){
t[x].ch[1] = merge(t[x].ch[1], y);
up(x); return x;
} else {
t[y].ch[0] = merge(x, t[y].ch[0]);
up(y); return y;
}
}
void insert(int val){
split(root, val, r1, r2);
root = merge(r1, merge(newnode(val), r2));
}
void delet(int val){
split(root, val-1, r1, r2), split(r2, val, r2, r3);
r2 = merge(t[r2].ch[0], t[r2].ch[1]);
root = merge(r1, merge(r2, r3));
}
int exgcd(int a, int b, int &x, int &y){
if(!b){ x = 1, y = 0; return a; }
int gcd = exgcd(b, a%b, x, y), tmp;
tmp = y, y = x-a/b*y, x = tmp;
return gcd;
}
int getv(int val){
int res = 0, node; split(root, val, r1, r2);
if(!t[r1].size){
node = r2;
while(t[node].ch[0]) node = t[node].ch[0];
} else {
node = r1;
while(t[node].ch[1]) node = t[node].ch[1];
}
root = merge(r1, r2); return t[node].val;
}
int mul(int a, int b, int mod){
int res = 0;
for(; b; b >>= 1, (a += a) %= mod)
if(b & 1) (res += a) %= mod;
return res;
}
void work(){
int x, y, v, M = 1, C, gcd; cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> hp[i];
for(int i = 1; i <= n; i++) cin >> p[i];
for(int i = 1; i <= n; i++) cin >> rew[i];
for(int i = 1; i <= m; i++) cin >> x, insert(x);
for(int i = 1; i <= n; i++){
v = getv(hp[i]), mx = max(mx, hp[i]/v+(hp[i]%v != 0));
C = (hp[i]-(mul(ans, v, p[i]))%p[i]+p[i])%p[i];
gcd = exgcd(M*v, p[i], x, y);
if(C % gcd != 0){ cout << -1 << endl; return; }
x = mul(x, C/gcd, p[i]), ans += x*M;
M *= p[i]/gcd, ans = (ans%M+M)%M;
delet(v), insert(rew[i]);
}
cerr << "mx=" << mx << endl;
if(ans < mx) ans += M*((mx-ans-1)/M+1);
cout << ans << endl;
}
void clear(){
for(int i = 1; i <= cnt; i++)
t[i].ch[0] = t[i].ch[1] = t[i].rd = t[i].size = t[i].val = 0;
ans = cnt = root = 0, mx = -inf;
}
_int main(){
freopen("dragon1.in", "r", stdin);
ios::sync_with_stdio(false);
srand(time(NULL));
cin >> T;
while(T--) work(), clear();
return 0;
}