BZOJ_5418_[Noi2018]屠龙勇士_exgcd+excrt
Description
www.lydsy.com/JudgeOnline/upload/noi2018day2.pdf
每次用哪吧剑显然用个set就搞定了。
对于每头龙，生命值ai，回血pi，剑的攻击力为atk，打的次数为ans。
显然有ans*atk-ai>=0&&pi|ans*atk-ai。
ans*atk+pi*y=ai (y<=0)。
要求y<=0的前提下ans尽量的小，是一个ax+by=n的形式，exgcd直接做。
然后得到n个方程，每个方程形如ans mod ai=bi。
ai不一定互质，直接上excrt。
感觉excrt一定程度上比crt还好理解。
大概就是个不断用exgcd合并的过程吧，自己想应该也能想出来。
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <set>
using namespace std;
typedef long long ll;
#define N 100050
int n,m,da[N];
ll a[N],p[N],mods[N],q[N];
ll Abs(ll x) {return x>0?x:-x;}
multiset<ll>S;
ll ch(ll x,ll y,ll mod) {
ll re=0; for(;y;y>>=1ll,x=(x+x)%mod) if(y&1ll) re=(re+x)%mod; return re;
}
void exgcd(ll a,ll b,ll &x,ll &y,ll &p) {
if(!b) {p=a; x=1; y=0; return ;}
exgcd(b,a%b,y,x,p),y-=a/b*x;
}
ll gcd(ll x,ll y) {return y?gcd(y,x%y):x;}
void init() {
S.clear();
}
int find(ll x) {
multiset<ll>::iterator it;
it=S.upper_bound(x);
if(it!=S.begin()) {
it--;
}
int tmp=*it;
S.erase(it);
return tmp;
}
ll exCRT() {
int i;
ll M=mods[1],A=q[1],t,d,x,y;
for(i=1;i<=n;i++) {
exgcd(M,mods[i],x,y,d);
if((q[i]-A)%d) return -1;
t=mods[i]/d;
x=(x%t+t)%t;
x=ch(x,(((q[i]-A)/d)%t+t)%t,t);
A=M*x+A; M=M/d*mods[i]; A=A%M;
}
A=(A%M+M)%M;
return A;
}
void solve() {
init();
scanf("%d%d",&n,&m);
int i,x;
for(i=1;i<=n;i++) scanf("%lld",&a[i]);
for(i=1;i<=n;i++) scanf("%lld",&p[i]);
for(i=1;i<=n;i++) scanf("%d",&da[i]);
for(i=1;i<=m;i++) {
scanf("%d",&x); S.insert(x);
}
ll mx=0;
int flg=0;
for(i=1;i<=n;i++) {
ll D=find(a[i]),P=p[i],A=a[i],X,Y,d,td=D,tp=P,ta=A;
if(p[i]==1) {mx=max(mx,(a[i]+D-1)/D); flg=1; S.insert(da[i]); continue;}
exgcd(D,P,X,Y,d);mods[i]=P/d;
if(A%d) {puts("-1"); return ;}
D/=d; P/=d; A/=d;
D=Abs(D);
Y=(ch(Y,A,D)+D)%D;
if(Y>0) Y-=D;
X=(ta-tp*Y)/td;
q[i]=X;
S.insert(da[i]);
}
if(flg) printf("%lld\n",mx);
else printf("%lld\n",exCRT());
}
int main() {
// freopen("dragon.in","r",stdin);
// freopen("dragon.out","w",stdout);
int T;
scanf("%d",&T);
while(T--) solve();
}