洛谷 P1516 青蛙的约会 题解【同余】【gcd】

点击量：108

    不定方程求通解的一道题

目录

题目描述

两只青蛙在网上相识了，它们聊得很开心，于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上，于是它们约定各自朝西跳，直到碰面为止。可是它们出发之前忘记了一件很重要的事情，既没有问清楚对方的特征，也没有约定见面的具体位置。不过青蛙们都是很乐观的，它们觉得只要一直朝着某个方向跳下去，总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上，不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙，你被要求写一个程序来判断这两只青蛙是否能够碰面，会在什么时候碰面。

 

我们把这两只青蛙分别叫做青蛙A和青蛙B，并且规定纬度线上东经0度处为原点，由东往西为正方向，单位长度1米，这样我们就得到了一条首尾相接的数轴。设青蛙A的出发点坐标是x，青蛙B的出发点坐标是y。青蛙A一次能跳m米，青蛙B一次能跳n米，两只青蛙跳一次所花费的时间相同。纬度线总长L米。现在要你求出它们跳了几次以后才会碰面。

 

输入输出格式

输入格式：

输入只包括一行5个整数x，y，m，n，L

 

其中0<x≠y < =2000000000，0 < m、n < =2000000000，0 < L < =2100000000。

 

输出格式：

输出碰面所需要的天数，如果永远不可能碰面则输出一行”Impossible”。

 

输入输出样例

输入样例#1：

1 2 3 4 5

输出样例#1：

4

题解：

    这个题目的条件很容易看出来，设两只青蛙的起点是$ s_1,s_2$，步长为$ x,y$（题目的参数看着容易混淆）。那它们相遇的条件就是跳$ t$步后$ s_1+tx\equiv s_2+ty(\mod L)$，求出$ t$的最小值。

    可以把这个条件转化为另一个问题，因为这个式子是在$ \mod L$的意义下进行的，把上面的式子移项得$ s_1-s_2+t(x-y)\equiv 0(\mod L)$，也就是$ s_1-s_2+t(x-y)= kL(k\in \mathbb{Z})\Rightarrow t(x-y)+kL=s_2-s_1$。这样就是一个不定方程了，其中$ (x-y),L,s_2-s_1$都是常数。

    用扩展欧几里得解这个方程，可以得到$ t,k$的一组特解，我们要求的是$ t$的最小正整数解。我们回归到最基础的不定方程$ ax+by=d,d=\gcd (a,b)$，一个求通解的办法就是让$ x$减去1，让$ y$去平衡它，这样可以得到$ a(x-1)+b(y+\frac ab)=d$，要找出使得$ x-p$为正整数且最小并满足$ y+p\times \frac ab$为整数，那就要让$ a|p$。因此$ p\in [0,x),a|p$，要让这个$ p$在范围内尽可能大，我们就要找到一个最大的$ q$使得$ aq<x$，这样最优解就是$ x-aq$了。

    实际可以用gcd的思想来求解这个过程。因为不定方程有无数组解，我们抽出两个$ \left\{\begin{matrix}ax+by=d\\ ax’+by’=d \end{matrix}\right.$，上下相减得到$ a(x-x_0)=b(y_0-y)$，再让两边同除$ \gcd (a,b)$，得到$ \frac a{\gcd (a,b)}(x-x_0)=b\frac b{\gcd (a,b)}(y_0-y)$。而$ \frac a{\gcd (a,b)} \bot \frac{b}{\gcd (a,b)}$，根据唯一分解定理可知$ \frac b{\gcd (a,b)}|(x-x_0)$，因此$ x_i=x_0+k\frac b{\gcd (a,b)}$。所以$ k_0=k_i\mod \frac b{\gcd (a,b)}$。

    最后注意如果$ d$是$ \gcd(a,b)$的倍数要乘上这个倍数。接着把原式中的”$ a,b$”代作$ (x-y),L$即可。

Code：

#include<cstdio>
#include<cstring>
long long exgcd(long long a,long long b,long long &x,long long &y)
{
    if(a==0)
    {
        x=1;
        y=0;
        return b;
    }
    long long d=exgcd(b%a,a,y,x);
    y-=b/a*x;
    return d;
}

int main()
{
    long long n,m,L,s1,s2;
    scanf("%lld%lld%lld%lld%lld",&s1,&s2,&n,&m,&L);
    if(n>m)//保证n<m，则系数>0
    {
        long long t=n;
        n=m;
        m=t;
        t=s1;
        s1=s2;
        s2=t;
    }
    long long a=m-n,b=L;
    long long x,y;
    long long t=exgcd(a,b,y,x);
    long long d=s1-s2;
    if(d%t!=0)
    {
        puts("Impossible");
        return 0;
    }
    d/=t;//最后答案要乘上的数
    L/=t;//求出最小解要mod上的数
    printf("%lld\n",((x*d)%L+L)%L);
    return 0;
}