青蛙的约会

一看这道题就是同余。然后就开始推方程qwq

\[x+mk\equiv y+nk\pmod L\]

\[x+mk-(y+nk)=Lz\]

\[(m-n)k+Lz=y-x\]

因为\(m-n\)、\(L\)、\(y-x\)都是已知的，所以这就是一个扩欧的模型。

扩欧就不说了，可以看这篇文章

总体来说，如果你看懂了扩欧，这倒题应该不难，不过细节蛮多的。

1. 不能乱用abs()，考虑好再用。

2. 千万不要变量重名，这导致了我20min的题做了2h。

3. 注意取模时的判负，这是（我认为的）难点

4. 开long long ! 开long long ! 开long long !

……应该就这些了。

Code

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;

typedef long long ll;

ll x_0,y_0,m,n,L;
ll g,x,y,ans;
ll a,b,c,mod;

inline void readx(ll &x)
{
    x=0;
    int s=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            s=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar();
    }
    x*=s;
}

inline ll gcd(ll a,ll b)
{
    if(b==0) return a;
    return gcd(b,a%b);
}

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

int main()
{
    readx(x_0);readx(y_0);
    readx(m);readx(n);readx(L);
    a=m-n,b=L,c=y_0-x_0;
    g=gcd(a,b);
    mod=abs(L/g);
    if(c%g)
    {
        printf("Impossible\n");
        return 0;
    }
    exgcd(a,b,x,y);
    ans=(x*(c/g)%mod+mod)%mod;
    printf("%lld\n",ans);
    return 0;
}

青蛙的约会

原文：https://www.cnblogs.com/oierwyh/p/11342085.html