题解 P4774 【[NOI2018]屠龙勇士】

场外选手休闲做题…… 拓展中国剩余定理板子题 _______________ ## 本题题解 ### 一些性质 首先我们会发现宰第i条龙时玩家的攻击力是一定的，因为每次使用的剑是确定的，每次得到的剑也是一定的。，因此我们可以使用$std::multiset$手动模拟宰龙的过程每次upper_bound出当前轮次的攻击力 接下来是求解最小的攻击次数的过程 我们发现龙在血量成为负数之后会自动定量回血这个设定十分像对负数取模 那么我们是否可以确定，一条龙被杀死当且仅当它的受到的伤害值模p为自己的血量呢？ 或者说，我们能不能列出一个像这样的含n个同余方程的同余方程组，求出这个同余方程组的最小正整数解x,然后说这就是最小的攻击次数呢？ ## $C_{i}x \equiv A_{i}(mod P_{i})$ 其中$C_{i}$是杀第i条龙时的攻击力，$A_{i}$是第i条龙初始的血量，$P_{i}$是第i条龙的恢复能力 然后我们发现并不是，因为题目当中并没保证$A_{i} \leq P_{i}$ 这样的话我们的同余限制条件只能保证攻击x次之后所有龙的血量模自身的恢复力都是0 但是如果$A_{i} > P_{i}$的话我们会发现我们攻击之后可能龙的血量从来没有到过负值，但是血量却的确模p为0了 ~~情况开始变得辣手~~ 此时是考验大家阅读理解能力的时刻了！ 仔细阅读出题人给出的数据表格，如果这个测试点不保证$A_{i} \leq P_{i}$的话，它一定会满足一个条件就是$P_{i}=1$ 这意味这我们可以大力特判掉这种情况，显然，在$P_{i}=1$的情况下，答案是 ## $Max_{i=1}^{n}( \lceil \frac{A_{i}}{C_{i}} \rceil )$ 就是所有龙血量为负的最小刀数取一个max就可以了 下面让我们集中精力解决$A_{i} \leq P_{i}$的情况 ___________________ ## 化简同余方程 在$A_{i} \leq P_{i}$这种情况下，大部分情况(除了几个臭名昭著的特例)，我们的同余方程都是生效的 换句话我们现在唯一要做的就是解下面同余方程组的最小正整数解 ## $C_{i}x \equiv A_{i}(mod P_{i})$ 你会发现这和标准中国剩余定理的方程不是非常一样，即使是可以处理模数不两两互质的拓展中国剩余定理，也只能处理这样的同余方程 ## $x \equiv A_{i}(mod P_{i})$ 换句话说x的系数必须是1 而且更加辣手的是$C_{i}$在模$P_{i}$意义下极有可能不存在逆元，所以我们也不能把$C_{i}$除掉 那么有什么办法可以化简这个东西吗？ (作为一名敢写noi2018的选手，理论上应该是会exgcd解一般的不定方程的，但是为了避免你的式子有些部分推错，这里还是介绍一下如何解一般的不定方程) 熟练的话可以跳过这一部分 ________________________ ### 前置知识:使用exgcd算法求解一般的不定方程 换句话说这里解决的问题是如何求方程$Ax+By=C (A,B,C >0)$的通解 但是众所周知，exgcd算法只能计算出方程$Ax+By=(A,B)$的一组特殊解 但是这里有一个结论是这个方程有解当且仅当 $C|(a,b)$ 所以我们可以稍稍换个元 令 $\frac{C}{(a,b)}x^{'}=x$,$\frac{C}{(a,b)}y^{'}=y$的话我们会发现我们的方程变成了这样 ## $A\frac{C}{(a,b)}x^{'} +B \frac{C}{(a,b)}y^{'}=(a,b)\frac{C}{(a,b)}$ 所以我们可以这样除掉了$\frac{C}{(a,b)}$ 于是方程就变成了可爱的$Ax^{'}+By^{'}=(A,B)$ 使用exgcd算法求出他的一个特解$sx^{'}$那么原方程的特解就是$\frac{C}{(a,b)}x^{'}$ 所以我们就得到了原方程的两个特解，可以借此构造原方程出所有的通解 ___________________________ 言归正传我们现在化简同余方程了,想办法把方程 ## $C_{i}x \equiv A_{i}(mod P_{i})$ 变成 ## $x \equiv A_{i}(mod P_{i})$ 第一个方程可以写成这样的不定方程的形式 ## $C_{i}x+P_{i}y = A_{i}$ 使用exgcd求出他的一组特解 $Sx,Sy$ 根据通解公式可以轻松的得到 ## $x=sx+k\frac{P_{i}}{(C_{i},P_{i})}$ 两边同时对$\frac{P_{i}}{(C_{i},P_{i})}$取模 ## $x \equiv sx (mod \frac{P_{i}}{(C_{i},P_{i})})$ 好了我们愉快的将同余方程化成了标准式，现在该考虑怎么解同余方程组了 ____________________________ ## Extended CRT:拓展中国剩余定理 我们现在要做的事情很简单，求同余方程组 ## $x \equiv C{i}(mod P_{i})$ 的最小正整数解，不保证两两互质 那么我们的思路事实上也是非常暴力的，将这些同余方程两两合并成一个同余方程，使得最后只剩下一个同余方程 所以我们的目标就是合并两个同余方程 ## $x \equiv C_{1}(mod P_{1})$ ## $x \equiv C_{2}(mod P_{2})$ 首先我们可以把同余方程写成不定方程 ## $x=C_{1}+ P_{1}y_{1}$ ## $x=C_{2}+ P_{2}y_{2}$ 由于事实上x同时满足两个方程，所以我们将两个方程联立 ## $P_{1}y_{1}=P_{2}y_{2}+C_{2}-C_{1}$ 根据不定方程的一些基本知识我们可以知道这个不定方程有解当且仅当$C_{2}-C_{1}|(P_{1},P_{2})$ 所以我们还是使用古老的套路两边同时除$(P_{1},P_{2})$这样的话，我们会发现式子变成了这样 ## $\frac{P_{1}}{(P_{1},P_{2})}y_{1}=\frac{P_{2}}{(P_{1},P_{2})}y_{2}+\frac{C_{2}-C_{1}}{(P_{1},P_{2})}$ 此时采用另一个老套路，两边同时对$\frac{P_{2}}{(P_{1},P_{2})}$取模 可以得到 ## $\frac{P_{1}}{(P_{1},P_{2})}y_{1}\equiv \frac{C_{2}-C_{1}}{(P_{1},P_{2})} (mod \frac{P_{2}}{(P_{1},P_{2})})$ 好的我们来看一下此时$\frac{P_{1}}{(P_{1},P_{2})}$和模数一定互质了，这意味着我们可以除逆元了 所以 ## $y_{1}\equiv inv(\frac{P_{1}}{(P_{1},P_{2})},\frac{P_{2}}{(P_{1},P_{2})})\frac{C_{2}-C_{1}}{(P_{1},P_{2})} (mod \frac{P_{2}}{(P_{1},P_{2})})$ 重新把这个同余方程写成不定方程 ## $y_{1}= inv(\frac{P_{1}}{(P_{1},P_{2})},\frac{P_{2}}{(P_{1},P_{2})})\frac{C_{2}-C_{1}}{(P_{1},P_{2})} +k\frac{P_{2}}{(P_{1},P_{2})}$ 然后代入到x的式子里 ## $x=C_{1}+ P_{1}y_{1}$ 得到的大概是这样的式子 ## $x=(inv(\frac{P_{1}}{(P_{1},P_{2})},\frac{P_{2}}{(P_{1},P_{2})})\frac{C_{2}-C_{1}}{(P_{1},P_{2})})\%\frac{P_{2}} {(P_{1},P_{2})} ×P_{1}+k\frac{P_{1}P_{2}}{(P_{1},P_{2})}+C_{1}$ 依旧是老套路，两边同时对$\frac{P_{1}P_{2}}{(P_{1},P_{2})}$取模消掉烦人的k 我们得到了 ## $x \equiv (inv(\frac{P_{1}}{(P_{1},P_{2})},\frac{P_{2}}{(P_{1},P_{2})})\frac{C_{2}-C_{1}}{(P_{1},P_{2})})\%\frac{P_{2}} {(P_{1},P_{2})} ×P_{1}+C_{1} (mod \frac{P_{1}P_{2}}{(P_{1},P_{2})})$ 此时我们发现这两个同余方程合并成了一个同余方程，此时我们就可以不停的合并同余方程来求解整个同余方程组的最小正整数解了 然后我们做完了这道题？ __________________________________ ## 一些小特例 如果所有的$P_{i}=A_{i}$的话我们解同余方程的结果将会是0 但是事实上这是不对的 直接求出杀死每条龙所需的刀数然后所有刀数求一个lcm即可 另一个小特例是我们的$C_{i}$是$P_{i}$的倍数时一般情况时杀不掉这条龙的 但是呢，如果$A_{i}=P_{i}$就很有趣了 此时这个方程等于没用，需要把它扔掉，换成一个没啥用的方程，比如$X\equiv 0(mod 1)$就行了 ________________________ ## 温馨提示 你的模数全部是longlong范围的，直接乘会爆longlong，请使用龟速乘法进行运算 上代码~ ```C #include<cstdio> #include<algorithm> #include<set> using namespace std;const int N=1e5+10;typedef long long ll; multiset <ll> s;int n;int m;ll mod[N];ll xs[N];ll cs[N];ll st[N];ll gif[N];int T; inline void exgcd(ll a,ll& x,ll b,ll& y)//exgcd {if(b==0){x=1;y=0;return;}exgcd(b,x,a%b,y);ll t=x;x=y;y=t-(a/b)*y;} inline ll gcd(ll a,ll b){if(a<b)swap(a,b);while(b){ll c=a%b;a=b;b=c;}return a;} inline ll inv(ll a,ll p){a%=p;ll x;ll y;exgcd(a,x,p,y);return ((x<0)?x+p:x);} inline ll mul(ll a,ll b,const ll& md)//龟速乘 {ll ret=0;b=b%md;b=(b>0)?b:b+md;for(;b;b>>=1,a=(a+a)%md)(ret+=a*(b&1))%=md;return ret;} inline void cfil(){printf("-1\n");return;} inline void spsolve()//特判 { ll res=0; for(int i=1;i<=n;i++)res=max(res,((cs[i]+xs[i]-1)/xs[i])); printf("%lld\n",res); } inline void spsolve2()//特判 { ll lc=1; for(int i=1;i<=n;i++) {ll ds=mod[i]/gcd(mod[i],xs[i]);lc=lc/gcd(lc,ds)*ds;} printf("%lld\n",lc); } inline void solve() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)scanf("%lld",&cs[i]); for(int i=1;i<=n;i++)scanf("%lld",&mod[i]); for(int i=1;i<=n;i++)scanf("%lld",&gif[i]); for(int i=1;i<=m;i++)scanf("%lld",&st[i]); for(int i=1;i<=m;i++)s.insert(st[i]); multiset <ll>:: iterator it; for(int i=1;i<=n;i++)//预处理方程的系数 { it=(cs[i]<(*s.begin()))?s.begin():(--s.upper_bound(cs[i])); xs[i]=*it;s.erase(it);s.insert(gif[i]); } for(int i=1;i<=m;i++)if(mod[i]!=cs[i])goto ski;spsolve2();return;ski:;//判一下p=a的情况 for(int i=1;i<=n;i++)if(mod[i]!=1)goto skp;spsolve();return;skp:;//判一下p=1的情况 for(int i=1;i<=n;i++)xs[i]%=mod[i]; for(int i=1;i<=n;i++)//检测是否有无用的方程 if(xs[i]==0){if(mod[i]==cs[i]){xs[i]=1;mod[i]=1;cs[i]=0;}else {cfil();return;}} for(int i=1;i<=n;i++)//化简同余方程 { ll sx;ll sy;ll g=gcd(xs[i],mod[i]);if(cs[i]%g!=0){cfil();return;} exgcd(xs[i],sx,mod[i],sy); mod[i]=mod[i]/g;sx=(sx%mod[i]+mod[i])%mod[i];cs[i]=mul(sx,cs[i]/g,mod[i]); } for(int i=1;i<=n-1;i++)//合并同余方程 { ll g=gcd(mod[i],mod[i+1]);if((cs[i+1]-cs[i])%g!=0){cfil();return;} ll ncs=mul(inv(mod[i]/g,mod[i+1]/g),(cs[i+1]-cs[i])/g,mod[i+1]/g); ll nmod=mod[i]/g*mod[i+1]; ncs=mul(ncs,mod[i],nmod);(ncs+=cs[i])%=nmod;cs[i+1]=ncs;mod[i+1]=nmod; }printf("%lld\n",cs[n]);return; } inline void clear(){s.clear();} int main(){scanf("%d",&T);for(int z=1;z<=T;z++)solve(),clear();return 0;}//拜拜程序~ ```