青蛙的约会

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1043 字

两只青蛙在长为L的环上同向西跳，求最早碰面所

一本通
例

正文

/*
原题：青蛙的约会 (POJ 1061)
题意：两只青蛙在长为 L 的环上同向西跳，求最早碰面所需的跳跃次数 t，无解输出 Impossible。
思路：列方程 (m-n)·t ≡ (y-x) (mod L)，用扩展欧几里得解线性同余方程。
      记 a=m-n, b=y-x；若 gcd(a,L) 不整除 b 则无解，否则求得最小非负 t。
复杂度：时间 O(log L)，空间 O(1)。
易错点：m-n 与 y-x 可能为负，需先对 L 取模归一化；
      无解时输出 Impossible（首字母大写），且要求最小非负整数解。
*/
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
// 扩展欧几里得：返回 gcd(a,b)，并求 a*x+b*y=gcd
ll exgcd(ll a, ll b, ll &x, ll &y){
    if(b==0){
        x=1;
        y=0;
        return a;
    }
    ll x1, y1;
    ll g=exgcd(b, a%b, x1, y1);
    x=y1;
    y=x1-(a/b)*y1;
    return g;
}
// 解 a*x ≡ b (mod m)，返回是否有解；有解时 x 为最小非负解
bool solve(ll a, ll b, ll m, ll &x){
    a=((a%m)+m)%m;
    b=((b%m)+m)%m;
    ll x0, y0;
    ll g=exgcd(a, m, x0, y0);
    if(b%g!=0){
        return false;
    }
    ll m1=m/g;
    x0=((x0%m1)+m1)%m1;
    x=(x0*(b/g))%m1;
    return true;
}
int main(){
    ll x, y, m, n, L;
    cin>>x>>y>>m>>n>>L;
    ll t;
    if(solve(m-n, y-x, L, t)){
        cout<<t<<"\n";
    }else{
        cout<<"Impossible\n";
    }
    return 0;
}

青蛙的约会

正文

一本通·提高篇的其它内容