P2421 [NOI2002]荒岛野人

· · 题解

思路

看一下数据范围，发现小得可怜，以至于我们可以枚举m时再枚举每对野人。于是这个题就变成了处理n^2m次P1516 青蛙的约会，只用每次判断一下，如果有两个野人可以活着相遇的话，就说明这个m不合适；如果没有，输出m就行了。

下面是AC代码： 

#include <bits/stdc++.h>
using namespace std;
int n,C[20],P[20],L[20];
int e_gcd(int a,int b,int& x,int& y)
{
    if(!b) {x=1,y=0;return a;}
    int ans=e_gcd(b,a%b,x,y);
    int t=x;x=y;y=t-(a/b)*y;
    return ans;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>C[i]>>P[i]>>L[i];
    for(int i=C[n];i<=1000000;i++)
    {
        int flag=0;
        for(int j=1;j<n;j++)
        {
            for(int k=j+1;k<=n;k++)
            {
                int a=P[k]-P[j],b=i,c=C[j]-C[k],x,y,gcd,minx;
                if(a<0) a=-a,c=-c;
                gcd=e_gcd(a,b,x,y);
                if(c%gcd!=0) continue;
                minx=((x*(c/gcd))%(b/gcd)+(b/gcd))%(b/gcd);
                if(minx<=min(L[j],L[k])) {flag=1;break;}
            }
            if(flag) break;
        }
        if(!flag) {printf("%d",i);break;}
    } 
}

接下来是对刚学的扩展欧几里得的一点整理

以这题为例,我们首先从基本问题出发：判断两个野人i和j何时相遇（能否相遇），其实就是求解方程

(C_i+tP_i)-(C_j+tP_j)=km

其中t为时间。也就是说在环形跑道上，相遇就是距离差为跑道周长的倍数时。把这个方程稍微变形一下得到

t(P_j-P_i)+km=C_i-C_j

如果我们设未知数t和k分别为x和y，常数(P_j-P_i)为a，m为b，(C_i-C_j)为c的话，可以发现这就是一个二元一次的不定方程，即

ax+by=c

那么要解决这题，我们需要知道这个方程：

我们先来看第一个问题

如果有整数解，那么

\begin{aligned} c &= ax+by\\ &= \gcd(a,b)\cdot(a_1x+b_1y) \end{aligned}

说明c是\gcd(a,b)的倍数。注意这里是有整数解的充分条件，即要有整数解c就必须是\gcd(a,b)的倍数。那我们干脆把c替换成\gcd(a,b)，解出来x和y后再扩倍。然后接下来的过程就十分的神奇，首先我们把a换成b，b换成a\mod b，即a-(a/b) \cdot b（这里的除号“/”表示结果向下取整），得到新的方程

bx+(a-(a/b) \cdot b)y=\gcd(a,b)

变形一下

ay+b(x-(a/b) \cdot y)=\gcd(a,b)

对比一下原来的方程，我们惊讶地发现因为常数都一样，所以我们可以由现在方程的解推导出原方程的解，而如果继续这个过程，这不就是辗转相除嘛！辗转相除的结果大家都知道，是a变成\gcd(a,b)，b变成0，而方程

\gcd(a,b) \cdot x+0 \cdot y=\gcd(a,b)

的解就很显然了，是

\begin{cases} x=1\\ y=0 \end{cases}

根据这个解，我们就可以，也肯定可以倒推出原方程的解了。现在再看这段代码 

int e_gcd(int a,int b,int& x,int& y)
{
    if(!b) {x=1,y=0;return a;}
    int ans=e_gcd(b,a%b,x,y);
    int t=x;x=y;y=t-(a/b)*y;
    return ans;
}

其实就是求\gcd(a,b)以及方程的一组特解的函数。当然最后别忘了乘上\dfrac{c}{\gcd(a,b)}。而如果c不是\gcd(a,b)的倍数，也就说明方程无整数解。

再来看第二个问题

求出了一组特解，再如何找到最小非负整数解呢？假设我们有

\begin{cases} ax_0+by_0=c\\ ax\ \ +by\,\,=c \end{cases}

一式减二式，得

\begin{aligned} a(x_0-x)+b(y_0-y)&=0\\ a(x_0-x)&=-b(y_0-y)\\ \dfrac{a}{\gcd(a,b)}(x_0-x)&=-\dfrac{b}{\gcd(a,b)}(y_0-y) \end{aligned}

注意到\dfrac{a}{\gcd(a,b)}与\dfrac{b}{\gcd(a,b)}互质，所以(x_0-x)是\dfrac{b}{\gcd(a,b)}的倍数，即

\begin{aligned} x_0-x&=k\dfrac{b}{\gcd(a,b)}\\ x_0&=k\dfrac{b}{\gcd(a,b)}+x \end{aligned}

那么x的最小非负整数解就是特解x_0 \mod \dfrac{b}{\gcd(a,b)}了。当然因为x_0可能是负数，所以代码里就长这样子 

minx=((x*(c/gcd))%(b/gcd)+(b/gcd))%(b/gcd);

最后一点要注意的，欧几里得算法求最大公约数只能针对两个非负整数，所以有了这句 

if(a<0) a=-a,c=-c;\\b绝对是正数

至此，我学到的扩展欧几里得算是梳理完了（欢迎大佬来补充），当然这个算法还有更多的应用，如乘法逆元、线性同余方程等，解不定方程算是最基础的一种了，必须牢牢掌握ヾ(•ω•`)o