您所在位置：主题：[讨论]青蛙的约会，提交不正确
five_cent
[专家分：0] 发布于 2010-01-05 14:49:00
/******************************************
题目：青蛙的约会
Time Limit: 1000ms
Memory limit: 10000kB
题目描述
两只青蛙在网上相识了，它们聊得很开心，于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上，于是它
们约定各自朝西跳，直到碰面为止。可是它们出发之前忘记了一件很重要的事情，既没有问清楚对方的特征，也没有约定见
面的具体位置。不过青蛙们都是很乐观的，它们觉得只要一直朝着某个方向跳下去，总能碰到对方的。但是除非这两只青蛙
在同一时间跳到同一点上，不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙，你被要求写一个程序来判断这两只青
蛙是否能够碰面，会在什么时候碰面。
我们把这两只青蛙分别叫做青蛙A和青蛙B，并且规定纬度线上东经0度处为原点，由东往西为正方向，单位长度1米，这样我
们就得到了一条首尾相接的数轴。设青蛙A的出发点坐标是x，青蛙B的出发点坐标是y。青蛙A一次能跳m米，青蛙B一次能跳n
米，两只青蛙跳一次所花费的时间相同。纬度线总长L米。现在要你求出它们跳了几次以后才会碰面。
输入
输入只包括一行5个整数x，y，m，n，L，其中x≠y < 2000000000，0 < m、n < 2000000000，0 < L < 2100000000。
输出
输出碰面所需要的跳跃次数，如果永远不可能碰面则输出一行"Impossible"
样例输入
1 2 3 4 5样例输出
4
*******************************************/
/******************************************
分析：
引入变量，跳跃次数：t
假如A、B相遇，则
(x+mt)%L==(y+nt)%L
<=> (x+mt)-(y+nt)==pL
<=> (x-y)+(m-n)t==pL
<=> (m-n)t+L(-p)==y-x
令m-n=>A,L=>B,y-x=>C
即求解 At+B(-p)=C 的整数解
定理：Extern Eculid Algorithm，存在整数A和B，存在整数x和y，使得Ax+By=Gcd(A,B)
命题：若A、B和C为整数。Ax+By=C存在整数解 <=> C%Gcd(A,B)=0
证明：
充分条件
A和B为整数，存在整数x和y，使得Ax+By=C；
则变换等式Gcd(A,B)*(A'x+B'y)=C,因A',B',x,y均为整数，因此C%Gcd(A,B)=0。得证。
必要条件
若C%Gcd(A,B)=0, 根据Extern Eculid Algorithm,Ax'+By'=Gcd(A,B),等式两边乘以c/Gcd(A,B),得证。
求解x和y，通解结构为
x = x0 + B/gcd(A,B)*k
y = y0 - A/gcd(A,B)*k (k为整数)
或者
x = x0 - B/gcd(A,B)*k
y = y0 + A/gcd(A,B)*k (k为整数)
Ax+By=A(x0+B/gcd(A,B)*k) + B(y0-A/gcd(A,B)*k)
或者
Ax+By=A(x0-B/gcd(A,B)*k) + B(y0+A/gcd(A,B)*k)
根据Extern Eculid Algorithm求解出Ax+By=Gcd(A,B)的特解x0'和y0'
之后两边乘上c/gcd(A,B),得到Ax+By=C的特解x0和y0
即A(x'*c/Gcd(A,B))+B(y'*c/Gcd(A,B))==Gcd(A,B)*c/Gcd(A,B);
因为题目要求的是最小的正整数解，因此，需要转换，观察通解结构可得，x%(B/gcd(A,B)*k)==某一数，该数必为最小整数解。
但是这里要注意 -1mod5在计算机上不是4，而是-1，因此，在考虑负数的时候，要将其转换成正数。
*******************************************/
#include<stdio.h>
//扩展欧几里得
__int64 exGcd(__int64 f,__int64 g,__int64 &A,__int64 &B)
{
if(f%g==0)
{
A=0;
B=1;
return g;
}
__int64 gcd =exGcd(g,f%g,A,B);
__int64 tempB=B;
B=A-B*f/g;
A=tempB;
return gcd;
}
int main()
{
__int64 x,y,m,n,L;
scanf("%I64d %I64d %I64d %I64d %I64d",&x,&y,&m,&n,&L);
__int64 gcd;
__int64 A,B;
__int64 a,b,c;
a=m-n;
b=L;
c=y-x;
if(a<0)
{
a=-a;
c=-c;
}
gcd=exGcd(b,a,B,A);
if(c%gcd!=0||m==n)
{
printf("Impossible");
}
else
{
b/=gcd;
c/=gcd;
A=A*c; //得到特解
A=A%b+b; //保证为正数，计算机的mod运算与真实的mod运算有点不大一样
A=A%b; //保证最小解
printf("%I64d",A);
}
return 0;
}
以上是我的分析和编写的代码，我查过网上的资料，除了讲一堆扩展欧几里得算法之外，都是讲得不清不楚的，总之一句话，提交不正确。
对比正确的代码，除了欧几里得算法我是判断余数为0时返回，而正确代码是除数为0时返回（其实一样的），其它的部分都一致。
题目：青蛙的约会
Time Limit: 1000ms
Memory limit: 10000kB
题目描述
两只青蛙在网上相识了，它们聊得很开心，于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上，于是它
们约定各自朝西跳，直到碰面为止。可是它们出发之前忘记了一件很重要的事情，既没有问清楚对方的特征，也没有约定见
面的具体位置。不过青蛙们都是很乐观的，它们觉得只要一直朝着某个方向跳下去，总能碰到对方的。但是除非这两只青蛙
在同一时间跳到同一点上，不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙，你被要求写一个程序来判断这两只青
蛙是否能够碰面，会在什么时候碰面。
我们把这两只青蛙分别叫做青蛙A和青蛙B，并且规定纬度线上东经0度处为原点，由东往西为正方向，单位长度1米，这样我
们就得到了一条首尾相接的数轴。设青蛙A的出发点坐标是x，青蛙B的出发点坐标是y。青蛙A一次能跳m米，青蛙B一次能跳n
米，两只青蛙跳一次所花费的时间相同。纬度线总长L米。现在要你求出它们跳了几次以后才会碰面。
输入
输入只包括一行5个整数x，y，m，n，L，其中x≠y < 2000000000，0 < m、n < 2000000000，0 < L < 2100000000。
输出
输出碰面所需要的跳跃次数，如果永远不可能碰面则输出一行"Impossible"
样例输入
1 2 3 4 5样例输出
4
*******************************************/
/******************************************
分析：
引入变量，跳跃次数：t
假如A、B相遇，则
(x+mt)%L==(y+nt)%L
<=> (x+mt)-(y+nt)==pL
<=> (x-y)+(m-n)t==pL
<=> (m-n)t+L(-p)==y-x
令m-n=>A,L=>B,y-x=>C
即求解 At+B(-p)=C 的整数解
定理：Extern Eculid Algorithm，存在整数A和B，存在整数x和y，使得Ax+By=Gcd(A,B)
命题：若A、B和C为整数。Ax+By=C存在整数解 <=> C%Gcd(A,B)=0
证明：
充分条件
A和B为整数，存在整数x和y，使得Ax+By=C；
则变换等式Gcd(A,B)*(A'x+B'y)=C,因A',B',x,y均为整数，因此C%Gcd(A,B)=0。得证。
必要条件
若C%Gcd(A,B)=0, 根据Extern Eculid Algorithm,Ax'+By'=Gcd(A,B),等式两边乘以c/Gcd(A,B),得证。
求解x和y，通解结构为
x = x0 + B/gcd(A,B)*k
y = y0 - A/gcd(A,B)*k (k为整数)
或者
x = x0 - B/gcd(A,B)*k
y = y0 + A/gcd(A,B)*k (k为整数)
Ax+By=A(x0+B/gcd(A,B)*k) + B(y0-A/gcd(A,B)*k)
或者
Ax+By=A(x0-B/gcd(A,B)*k) + B(y0+A/gcd(A,B)*k)
根据Extern Eculid Algorithm求解出Ax+By=Gcd(A,B)的特解x0'和y0'
之后两边乘上c/gcd(A,B),得到Ax+By=C的特解x0和y0
即A(x'*c/Gcd(A,B))+B(y'*c/Gcd(A,B))==Gcd(A,B)*c/Gcd(A,B);
因为题目要求的是最小的正整数解，因此，需要转换，观察通解结构可得，x%(B/gcd(A,B)*k)==某一数，该数必为最小整数解。
但是这里要注意 -1mod5在计算机上不是4，而是-1，因此，在考虑负数的时候，要将其转换成正数。
*******************************************/
#include<stdio.h>
//扩展欧几里得
__int64 exGcd(__int64 f,__int64 g,__int64 &A,__int64 &B)
{
if(f%g==0)
{
A=0;
B=1;
return g;
}
__int64 gcd =exGcd(g,f%g,A,B);
__int64 tempB=B;
B=A-B*f/g;
A=tempB;
return gcd;
}
int main()
{
__int64 x,y,m,n,L;
scanf("%I64d %I64d %I64d %I64d %I64d",&x,&y,&m,&n,&L);
__int64 gcd;
__int64 A,B;
__int64 a,b,c;
a=m-n;
b=L;
c=y-x;
if(a<0)
{
a=-a;
c=-c;
}
gcd=exGcd(b,a,B,A);
if(c%gcd!=0||m==n)
{
printf("Impossible");
}
else
{
b/=gcd;
c/=gcd;
A=A*c; //得到特解
A=A%b+b; //保证为正数，计算机的mod运算与真实的mod运算有点不大一样
A=A%b; //保证最小解
printf("%I64d",A);
}
return 0;
}
以上是我的分析和编写的代码，我查过网上的资料，除了讲一堆扩展欧几里得算法之外，都是讲得不清不楚的，总之一句话，提交不正确。
对比正确的代码，除了欧几里得算法我是判断余数为0时返回，而正确代码是除数为0时返回（其实一样的），其它的部分都一致。