POJ1061 青蛙的约会

文章目录

1. 1. 题意
2. 2. 分析

原题

题意

青蛙1从x开始跳，每次跳m，青蛙2从y开始跳，每次跳n，环行线总长L

分析

裸的二元一次不定方程，如果两个青蛙的步数相同，则永远不可能，若(x-y)%gcd(n-m,l)!=0则永无正整数解

(x+pm)-(y+pn)=kl   
p(n-m)+kl=x-y

wa1:gcd(a,b)应当存起来。。因为后面会改变
wa2：因为a,b可能是负数，所以原本的gcd就是写错了。。。

*注意：因为次数不可能为负数，所以需要对求出来的特解进行处理,求出最小正整数解
*

#include <cstdio>
long long gcd(long long a,long long b){return b==0?a:gcd(b,a%b);}

void exgcd(long long a,long long b,long long &x,long long &y){
    if(b==0){
        x=1,y=0;
        return;
    }
    exgcd(b,a%b,x,y);
    long long temp=x;
    x=y;
    y=temp-a/b*y;
    return;
}
int main(){

    long long x,y,m,n,t,l,ans,a,b,c,d;
    while(scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&l)!=EOF){
        ans=x-y;
        a=n-m;
        b=l;
        t=gcd(a,b);
        if(ans%t!=0||m==n){
            printf("Impossible\n");
        }
        else{
            a/=t;
            b/=t;
            ans/=t;
            exgcd(a,b,c,d);
            c=((ans*c)%b+b)%b;
            if(c<0){
                c+=b;
            }
            printf("%lld\n",c);
        }
    }
    return 0;
}