青蛙的约会 POJ - 1061
扩展欧几里得
题目描述：两只青蛙都沿着一个圆轨道往西跳，第一个青蛙一步调m,第二个青蛙一步跳n,初始时第一个在位置x,第二个在位置y，轨道长度是L,求跳多少次他俩相遇。
解题思路：扩展欧几里得。在此处我令第一个青蛙位置为大写的X，第二个为大写的Y，所求的次数为小写的x.方程 (X+mx)%L=（Y+nx）%L -> X+mx=pL+(Y+nx)%L ->
X+mx-pL=(Y+nx)%L -> X+mx-pL+qL=Y+nx ->移项整理得
(m-n)x+(p-q)L=Y-X; 另（m-n）=a,(p-q)=y,L=b,(Y-X)=c,就变成大家熟悉ax+by=c的形式了。
注意：WA了一次是因为数据类型，全部换成long long 后没问题。所以以后处理类似的问题数据都选long long 吧，因为尽管题目给的变量数据不会超出int 范围，但难保运算过程中超出int 范围。
代码如下：
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
long long exgcd(long long a,long long b,long long &x,long long &y)
{
if(b==0)
{
x=1;
y=0;
return a;
}
else
{
long long ans=exgcd(b,a%b,x,y);
long long t=y;
y=x-(a/b)*y;
x=t;
return ans;
}
}
int main()
{
long long X,Y,m,n,L,x,y;
scanf("%lld %lld %lld %lld %lld",&X,&Y,&m,&n,&L);
long long a=m-n,b=L,c=Y-X;//此处该是正数就是正数，该是负数就是负数。
long long g=exgcd(a,b,x,y);
if(c%g) cout << "Impossible" << endl;
else
{
c/=g;
b/=g;
x=x*c%b;
x=(x+abs(b))%abs(b);
cout << x << endl;
}
return 0;
}
投递腾讯等公司10个岗位 >