题目链接
http://poj.org/problem?id=1061
题目类型
扩展欧几里得算法
解题思路
设青蛙A为速度快的那只，则有(m - n) * t - k * l = y - x
令a = m - n, b = l, c = y - c则把原方程转化为ax + by = c
我们需要判断该方程是否有解，如果有我们要求一个关于x的最小正数解
求解过程就用到了我们的扩展欧几里得算法，直接上板子即可
AC代码
#include<stdio.h>
#include<algorithm>
using namespace std;
typedef long long LL;
void gcdEx(LL a,LL b,LL &d,LL &x,LL &y)
{
if(!b)
{
x = 1; y = 0;
d = a;
}
else
{
gcdEx(b,a % b,d,y,x);
y -= x * (a / b);
}
}
int main()
{
LL m,n,x,y,l;
while(scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&l) == 5)
{
if(m < n)
{
swap(x,y);
swap(m,n);
}
LL g;
LL a = m - n;
LL b = l;
LL c = y - x;
gcdEx(a,b,g,x,y);
if(c % g) printf("Impossible\n");
else
{
x = x * c / g;
LL b1 = b / g;
if(x > 0) x = x % b1;
else x = x % b1 + b1;
printf("%lld\n",x);
}
}
return 0;
}
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
