【详解】POJ-1061-青蛙的约会【扩展欧几里得算法】数学

【【详解】POJ-1061-青蛙的约会【扩展欧几里得算法】】POJ-1061-青蛙的约会【扩展欧几里得算法】
模板：

int gcd(int a, int b) { if(b == 0) return a; return gcd(b, a % b); }

扩展模板：

int exgcd(int a, int b, int &x, int &y){ if(b == 0){ x = 1; y = 0; return a; } int r = exgcd(b, a % b, x, y); int t = x; x = y; y = t - a / b * y; return r; }

对于上页代码：
a’ = b, b’ = a % b 而言，我们求得 x, y使得 a’x + b’y = gcd(a’, b’)
由于b’ = a % b = a - a / b * b (这里的/是程序设计语言中的除法)
那么可以得到:
a’x + b’y = gcd(a’, b’) ===>
bx + (a - a / b * b)y = gcd(a’, b’) = gcd(a, b) ===>
ay +b(x - a / b*y) = gcd(a, b)
因此对于a和b而言，他们的相对应的p，q分别是 y和(x-a/b*y).
解 x，y的方法的理解：
1、显然当 b=0，gcd（a，b）=a。此时 x=1，y=0；
也就是1*a+0*b = a
2、设 ax1+by1=gcd(a,b);
在下一个exgcd里bx2+(a mod b)y2=gcd(b,a mod b);
根据欧几里德原理有 gcd(a,b)=gcd(b,a mod b);
则:ax1+by1=bx2+(a mod b)y2;
即:ax1+by1=bx2+(a-(a/b)*b)y2=ay2+bx2-(a/b)*by2;
根据恒等定理得：x1=y2; y1=x2-(a/b)*y2;
这样我们就得到解 x1,y1 的方法：x1，y1 的值基于 x2，y2
设时间为t，则两个青蛙的位置分别为(x+mt)mod L、(y+nt) mod L，相遇即是(x+mt)%L=(y+nt)%L，即(m-n)*t+k*L=y-x。
OK，现在已经符合ax+by=c的方程了，设a=m-n，b=L，c=y-x，
由于ax+by=gcd(a,b)而不是c,因此只有当c|gcd(a,b)时,有解
此时方程俩边同时乘c/gcd(a,b),便可得c/gcd(a,b)*(ax+by)=c
注意t>0，所以要用通解公式得出最小正整数。最后注意用long long~

#include #include #include #include #define ll long long int using namespace std; long long exgcd(ll a,ll b,ll &x,ll &y) { if(b==0) { x=1; y=0; return a; } ll r=exgcd(b,a%b,y,x); y-=x*(a/b); return r; } int main() { ll x,y,m,n,L; ll a,b,c,gcd; while(scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&L)!=EOF) { a=m-n; b=L; c=y-x; if(a<0) { a=-a; c=-c; } gcd=exgcd(a,b,x,y); if(c%gcd!=0) printf("Impossible"); else { x=x*c/gcd; int t=b/gcd; if(x>=0) x=x%t; else x=x%t+t; printf("%lld\n",x); } } return 0; }