解题报告 P1516 青蛙的约会

题目内容

长度为 L 的首尾相接的数轴上有两只青蛙，坐标分别为 x，y，分别每次能往前跳 m 和 n 个单位长度，求最少跳几次后相遇。

解题思路

不难得到题目需要我们解如下关于 k 的方程的最小正整数解：

x+km\equiv y+kn\pmod L

化简可得到

(m-n)k\equiv y-x\pmod L

也就是说，我们只要找得到方程

(m-n)k+Lj=y-x

（其中 j\in\mathbb{Z}）的最小正整数解，即为答案，而这个方程可以使用拓展欧几里得进行求解。

如果 \gcd(m-n,L)\not|(y-x)，说明该方程无解。

为了简化符号表达，接下来令 a=m-n，b=L，c=y-x，X 为我们要求的 k，Y 为上文的 j。方程便被化为

aX+bY=c

先使用拓欧求出 aX+bY=\gcd(a,b) 的一个特解 X_0，则该方程的最小正整数解为 X_0\bmod\frac{b}{\gcd(a,b)}，最后需要的结果再乘上 \frac{c}{\gcd(a,b)} 即可

输出时注意要避免负数的输出，不开 long long 会炸掉

#include <cstdio>

typedef long long ll;
ll X,Y,M,N,L,gcd;

void exgcd(ll &x,ll &y,ll a,ll b)
{
    if(!b)
        x=1,y=0,gcd=a;
    else
        exgcd(y,x,b,a%b),y-=a/b*x;
}

int main()
{
    scanf("%lld %lld %lld %lld %lld",&X,&Y,&M,&N,&L);
    ll x,y;
    ll a=M-N,c=Y-X,&b=L;
    if(a<0)
        a=-a,c=-c ;
    exgcd(x,y,a,b);
    if(c%gcd)
    {
        printf("Impossible\n");
        return 0;
    }
    printf("%lld\n",(x%(b/gcd)*c/gcd+b/gcd)%(b/gcd));
    return 0;
}