题意:
青蛙 A 和 青蛙 B ,在同一纬度按照相同方向跳跃相同步数,A的起点为X ,每一步距离为m,B的起点为Y,每一步距离为 n,一圈的长度为L,求最小跳跃步数。
思路:
一开始按照追击问题来写,结果发现会求出来小数,而且按照追击问题写的话,一圈就能相遇,但是!青蛙的步数可没有小数,而且青蛙是跳跃的,显然不能在空中相遇吧。
所以咧,先列出一个追击的式子 ,设步数为 t ,整数为K(转了K圈以后他们才到同一个地方)
t * m + x = t * n + y + k * L ===> t * ( n - m ) + k * L = x - y
贝祖公式 a * x +b * y = gcd ( a , b )
当 a * x +b * y = W 时,W % gcd(a,b) = = 0
x 的最小正整数解就是要求的答案
再看扩展欧几里得
long long exgcd(long long a,long long b)
{
if(b==0)
{
x=1;
y=0;
return a;
}
long long r=exgcd(b,a%b);
long long temp=x;
x=y;
y=(temp-a/b*y);
return r;
}
在求a , b 的最大公约数的时候 a % b = a - (a / b) * b
a * x + b * y =gcd(a,b) ==> b * x1 + a%b * y1 = gcd( a , b )
展开得 :a * y1 +b[ x1 - ( a / b) * y1 ] = gcd( a , b )
可得 x = y1 , y= [ x1 - ( a / b) * y1 ] ;
当余数为也就是b 为 0,返回值 为 a,根据 a * x + b * y =gcd(a,b),x=1,y=0,在通过递归的回溯,计算上一个状态的 x 和 y。
最后求得的 x 可能是负数那就要找最小正整数解。
当一组解为(x, y ),那么通解公式就是 (x+b/gcd , y + a/gcd)
b/gcd 为整数的时候,它是x的解的一个周期,根据这个周期找到第一个正整数。
long long t=l/k;//根据通解公式 (x1,y1)为一组通解,则(x1+b/gcd*k,y1+a/gcd*k)也是解
if(t<0)//x的解得周期为b/gcd y的解的周期 a/gcd 则任意解 x 对b/gcd取模,得出最小解,取正就ok了
t=-1*t;
printf("%lld\n",(x%t+t)%t);//取模运算 带入数字,x=-5,t=3,去理解
看代码:
">long long x;long long y;
long long exgcd(long long a,long long b)
{
if(b==0)
{
x=1;
y=0;
return a;
}
long long r=exgcd(b,a%b);
long long temp=x;
x=y;
y=(temp-a/b*y);
return r;
}
int main()
{
long long n,m,l,a,b;
while(~scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&l))
{
b=m-n;
a=y-x;
long long k=exgcd(b,l);
if(a%k)
printf("Impossible\n");
else
{
x=x*a/k;
long long t=l/k;//根据通解公式 (x1,y1)为一组通解,则(x1+b/gcd*k,y1+a/gcd*k)也是解
if(t<0)//x的解得周期为b/gcd y的解的周期 a/gcd 则任意解 x 对b/gcd取模,得出最小解,取正就ok了
t=-1*t;
printf("%lld\n",(x%t+t)%t);
}
}
return 0;
}