题目传送门

大致题意:

$A,B$分别从一条周长为$l$的环形跑道的位置$x,y$出发,每单位时间分别可以移动$m,n$个单位。问最少要经过多少个单位时间后$A,B$才能位置重合。视作$A,B$只在每个单位时间结束后移动。


注意到是环形跑道,所以真实的位置需要对长度取模,如果取模后相等就说明位置重合。

假设最终答案为$k$。那么显然$x+km\equiv y+kn\pmod l$

然后来移项。$km-kn\equiv y-x\pmod l$。

左边提个$k$出来。$k(m-n)\equiv y-x\pmod l$。

是不是有点熟悉了?

把$(m-n)$作为$a$,$y-x$作为$c$,$l$作为$b$。方程就变为了$ax\equiv c\pmod b$的形式。($x$即为最终答案)

考虑输出$Impossible$的情况,也就是方程没有非负数解的时候,即$c\mod gcd(a,b) \ne 0$,判一下就可以了。

于是用扩欧得到一组特解。因为不是$ax\equiv 1\pmod b$的形式,所以我们要进行一些处理。

所以原方程的特解是$x*\lfloor \frac{c}{gcd(a,b)} \rfloor$。

再让它满足最小非负:对$\lfloor \frac{b}{gcd(a,b)} \rfloor$取模,加上它,再对他取模。或者用$while$先一直加它到非负,再取模一次就好了。

丑的可怜的代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int gcd(int a,int b){return !b?a:gcd(b,a%b);}
int exgcd(int a,int b,int &x,int &y){return !b?(x=1,y=0):(exgcd(b,a%b,y,x),y-=a/b*x);}
signed main()
{
    int x,y,m,n,b;
    cin>>x>>y>>m>>n>>b;
    int a=m-n,c=y-x;
    if(a<0)a=-a,c=-c;
    int kk,kkk;
    exgcd(a,b,kk,kkk);
    int k=gcd(a,b);
    if(c%k!=0)
    {
        puts("Impossible");
        return 0;
    }
    int mod=b/k;
    int ans=((kk*(c/k)%mod)+mod)%mod;
    printf("%lld\n",ans);
    return 0;
}
最后修改:2020 年 08 月 05 日 08 : 38 PM