poj1061（扩展欧基里德定理）

题目链接：https://vjudge.net/problem/POJ-1061

题意：在一个首位相接的坐标轴上，A、B开始时分别位于X,Y处，每个单位时间向右移动m,n米，问是否能相遇，坐标轴长L。

思路：与poj2115几乎一样，扩展欧基里德模板题。题意即X+m*x=Y+n*x (mod L)，x为最短相遇时间，转换后：(m-n)*x+L*y=Y-X (mod L)，令a=m-n,b=L,c=Y-X，可通过扩展欧基里德定理计算出a*x+b*y=gcd(a,b)，令d=gcd(a,b)。则原题有解等价与d整除c，且解为 ((c/d*x)%tmp+tmp)%tmp，tmp=abs(b/d)，因为a可能小于0，所以计算出来的c也可能小于0，所以tmp要取绝对值。

AC代码：

#include<cstdio>

using namespace std;

typedef long long LL;

LL X,Y,m,n,L;

void ex_gcd(LL a,LL b,LL &x,LL &y,LL &d){

    if(!b) x=,y=,d=a;

    else{ex_gcd(b,a%b,y,x,d);y-=x*(a/b);}

}

int main(){

    scanf("%lld%lld%lld%lld%lld",&X,&Y,&m,&n,&L);

    LL a=m-n,b=L,c=Y-X,x,y,d;

    ex_gcd(a,b,x,y,d);

    LL tmp=b/d;

    if(tmp<) tmp=-tmp;

    if(c%d==)

        printf("%lld\n",((c/d*x)%tmp+tmp)%tmp);

    else

        printf("Impossible\n");

    return ;

}

巴特西

poj1061（扩展欧基里德定理）

最新文章

热门文章