【excrt】屠龙勇士（luogu 4774）

本文主要是介绍【excrt】屠龙勇士（luogu 4774），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

正题

luogu 4774

题目大意

有n条龙，第i条血量为 $a_i$ ，回血量为 $b_i$ ，杀死后掉落伤害为 $D_i$ 的刀，初始有若干刀

杀第i条龙要用现有伤害比 $a_i$ 小的刀中伤害最大的（如果没有就用伤害最小的），对第i条龙造成x次伤害后，龙会连续回血，每次回 $b_i$ ，若某一时刻龙的血量为0，那么该龙死亡

现在问你找到最小的x，使其满足能杀死所有龙

解题思路

对于每条龙所选刀，可以用multiset存现有刀，然后直接查询符合的

设所选刀伤害为 $d_i$ ，那么答案就是要求：

$-(a_i-d_i\times x)\equiv 0(\mod b_i)$

$d_i\times x\equiv a_i(\mod b_i)$

该式子形如crt的式子

因为 $b_i$ 不保证互质，所以求解要用excrt

代码

#include<set>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll __int128
#define N 100100
using namespace std;
ll T, n, m, p, x, y, g, X, mx, a[N], mo[N], b[N];
multiset<ll>d;
ll exgcd(ll a,ll b, ll &x, ll &y)
{if(!b){x = 1;y = 0;return a;}ll k = exgcd(b, a % b, x, y);ll z = y;y = x - a / b * y;x = z;return k;
}
ll read()
{char ch=getchar();ll ds=0,fs=1;while (ch<'0'||ch>'9') {if (ch=='-') fs=-1;ch=getchar();}while (ch>='0'&&ch<='9') ds=(ds<<3)+(ds<<1)+ch-48,ch=getchar();return ds*fs;
}
void writ(ll c) {if (c/10) writ(c/10); putchar(c%10+48); return;}
void write(ll s) {s<0?putchar(45),writ(-s):writ(s); putchar(10);return;}
int main()
{T = read();while(T--){mx = 0;p = 0;d.clear();n = read();m = read();for (ll i = 1; i <= n; ++i)a[i] = read();for (ll i = 1; i <= n; ++i)mo[i] = read();for (ll i = 1; i <= n; ++i)b[i] = read();for (ll i = 1; i <= m; ++i)d.insert(read());for (ll i = 1; i <= n; ++i)//找刀{multiset<ll>::iterator it = d.upper_bound(a[i]);if (it == d.begin()) x = *it;else x = *--it;d.erase(it);d.insert(b[i]);b[i] = x;mx = max(mx, (a[i] - 1) / b[i] + 1);//最小刀数}m = 1;X = 0;for (ll i = 1; i <= n; ++i)//excrt{g = exgcd(b[i] * m, mo[i], x, y);if ((a[i] - X * b[i]) % g){p = 1;break;}x = x * ((a[i] - X * b[i]) / g) % (mo[i] / g);X = X + x * m;m = m * (mo[i] / g);X = (X % m + m) % m;//最小解}if (p){puts("-1");continue;}if (X < mx) X += (mx - X + m - 1) / m * m;//保证剩余血量>0write(X);}return 0;
}