题目内容

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

解题思路

不难得到题目需要我们解如下关于 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-nb=Lc=y-xX 为我们要求的 kY 为上文的 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;
}
最后修改日期:2020年9月17日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。