POJ(1061 青蛙的约会 扩展欧几里德求解不定方程)

spoiler posted @ 2011年5月06日 16:15 in 数论 , 6912 阅读

题目大意:

Description

两只青蛙在网上相识了,它 们聊得很开心,于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上,于是它们约定各自朝西跳,直到碰面为止。可是它们出发之前忘记了一件很 重要的事情,既没有问清楚对方的特征,也没有约定见面的具体位置。不过青蛙们都是很乐观的,它们觉得只要一直朝着某个方向跳下去,总能碰到对方的。但是除 非这两只青蛙在同一时间跳到同一点上,不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙,你被要求写一个程序来判断这两只青蛙是否能够碰面,会在什么 时候碰面。
我们把这两只青蛙分别叫做青蛙A和青蛙B,并且规定纬度线上东经0度处为原点,由东往西为正方向,单位长度1米,这样我们就得到了一条首尾相接的 数轴。设青蛙A的出发点坐标是x,青蛙B的出发点坐标是y。青蛙A一次能跳m米,青蛙B一次能跳n米,两只青蛙跳一次所花费的时间相同。纬度线总长L米。 现在要你求出它们跳了几次以后才会碰面。

Input

输入只包括一行5个整数x,y,m,n,L,其中x≠y < 2000000000,0 < m、n < 2000000000,0 < L < 2100000000。
 
题目分析:首先青蛙A B 相遇必须满足:( x+ m*s  ) - ( n*s + y ) = k*L;  这里 s 代表他们跳的步数,k代表他们在第几圈 相遇!
                这里如果你想尝试枚举的话,只能说这里的浮动性太大了,谁能确定 s 的范围呢,又有谁知道 最小的 s 是多大呢,这个也许
                会很大的!所以只能 用 扩展的欧几里德 求这个不定方程!
求解 不定方程: ( x+ m*s  ) - ( n*s + y ) = k*L   首先我们把这个方程变形 : s * ( n - m)  + k* L = x -y ; 注意观察这个方程, 这就是所谓的线性同余方程, 对于这种方程,如果有解 必须满足 (x - y)% gcd (  n-m, L )==0 不然就无解, 输出Imposible!
这里通过看别人的总结 与自己看书,介绍一下怎么用欧几里德扩展求不定方程:
设标准方程式为: a*x +b*y =d   (a,b已知)
第一步:
           首先求出gcd(a,b) ,然后化简方程,使得a/=gcd(a,b); b/=gcd(a,b); d/=gcd(a,b);
           这样的话化简过后的 a,b就是互质的啦!(下面说的a,b 都是已经化简过的 注意哦 不再声明了)
第二步:
           先求出 a*x+b*y=gcd(a,b) 的一组特解,也就是方程 a*x+b*y=1 的一个特解 (a,b互质 所以最大公约数为1!)
           然后将特解(x0, y0) 代入方程,并变形: a* x0 *d + b* y0 *d= d 再仔细看看, (x=x0*n ,y=y0*n)  这不是
           第一步里面 化简后的标准方程的一组解麽?然后我已经求得 标准方程的一组解了,继续讨论 解系里面的最小值吧!
第三步:
         根据解系的 公式: x =x1 + b* t ; y =y1 - a *t; 我们首先假设他最小的解x=0 ,然后求出 此时的 t=-x1/b; 然后带入
          求最小的解x=x1+b*t=x1 - b*t ;因为此时的t为 负数, 减去他的 负数,就是等于加上他!
代码+部分注释:
#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
long long gcd(long long a,long long b){
	long long c;
	if(a<b){
		c=a;	a=b;
		b=c;
	}
	while(b){
		c=b;
		b=a%b;
		a=c;
	}
	return a;
}
long long extended_gcd(long long a,long long b,long long &x,long long &y){
	long long ans,t;
	if(b==0){
		x=1;	y=0;
		return a;
	}
	else{
		ans=extended_gcd(b,a%b,x,y);
		t=x;	x=y;
		y=t-(a/b)*y;
	}
	return ans;
}
int main(){
	long long x,y,m,n,l;
	long long a,b,d,k,s,t;
	while(scanf("%lld %lld %lld %lld %lld",&x,&y,&m,&n,&l)!=EOF){
		a=n-m;
		b=l;
		d=x-y;
		long long r=gcd(a,b);
		if(d%r!=0){
			printf("Impossible\n");
			continue;
		}
		a/=r;
		b/=r;
		d/=r;
		extended_gcd(a,b,s,k);
		s=s*d;
		k=k*d;
		t=s/b;
		s=s-t*b;
		if(s<0)
			s+=b;
		printf("%lld\n",s);
	}
	return 0;
}

 

Avatar_small
hello kity 说:
2011年5月06日 16:43

第一次深入点的学习数论,以后继续下去,加油!每个知识块都大量练习!给自己加油!

Avatar_small
qiqijianglu 说:
2011年6月06日 02:05

你能帮我解释下这里吗?
if(s<0)
s+=b;

Avatar_small
hello kity 说:
2011年6月12日 15:18

如果s小于0 这里就不是合法解了 然后要加上一个b 让他变成最小的正解 呵呵

Avatar_small
足士 说:
2013年4月21日 01:47

代码应该还可以简化,你解释的字让我不容易看清,建议改种颜色。

Avatar_small
HCOONa 说:
2013年8月12日 05:56

你这个答案基本上正确,但是有些数据有问题,比如:
x=3, y=1, m=2, n=1, L=4
你的答案是-6,正确答案应该是2。
而且其实不用long long,int就够用了。

Avatar_small
HCOONa 说:
2013年8月12日 06:08

如果t=s/b是正值的话,你这个就没问题,如果是负值就错了,应该是t=static_cast<int>(floor(static_cast<double>(s)/b));

Avatar_small
HCOONa 说:
2013年8月12日 06:13

好像还是不对……

Avatar_small
HCOONa 说:
2013年8月12日 06:20

找到问题了,你gcd算出来的r和extended_gcd算出来的r不一样,一个是-1,一个是+1。你从一开始就用extended_gcd算出来的r就好了。

Avatar_small
HCOONa 说:
2013年8月12日 06:28

囧……好象还是不对……

Avatar_small
HCOONa 说:
2013年8月12日 15:00

这下终于明白了,你这t是反着的,所以应该用t=static_cast<int>(ceil(static_cast<double>(s)/b));


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter