(exgcd)青蛙的约会
拓展gcd详解传送门
思路：设时间为t，则两个青蛙的位置分别为(x+mt)mod L、(y+nt) mod L，相遇即是(x+mt)%L=(y+nt)%L，即(m-n)t+kL=y-x。
OK，现在已经符合ax+by=c的方程了，设a=m-n，b=L，c=y-x，然后套用模板求出特解t的值，注意t>0，所以要用通解公式得出最小正整数
解释<1>
gcd 只对非负整数有意义，所以如果a<0等式两边要同时取负，a,c都要变成相反数；b本来就是正数，不用变也不能变。
解释<2>
利用exgcd，我们可以求解ax+by=g的一个解，然后
等式两边同乘c/g，得a* cx/g+b* cy/g=c
那么，x=cx/g就是ax+by=c中x的一个解
如何由一个解得到其它解呢？有一个恒等式a(x+db)+b(y−da)=c
在保证db,da都是整数的情况下，我们让d最小，就可以得到所有的整数解，那么d=n/g。 (n是一个整数)
如果解出的x>0，那么最小非负整数解等于x mod b/g；否则等于x mod b/g+b/g（这个很好理解，只要满足x大于0，我们通过db来调节x使x最小）
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
typedef long long ll;
ll exgcd(ll a, ll b, ll &x, ll &y)
{
if(b==0)
{
x=1;y=0;
return a;
}
int r=exgcd(b,a%b,x,y);
ll temp=y;
y=x-(a/b)*y;
x=temp;
return r;
}
int main()
{
ll x,y,m,n,l,a,b,c,p;
cin>>x>>y>>m>>n>>l;
a=m-n;
b=l;
c=y-x;
if(a<0) //<1>
{
a=-a;
c=-c;
}
p = exgcd(a,b,x,y);
if(c%p!=0) {
printf("Impossible\n");
}
else{
x=x*c/p;
ll d=b/p;
if(x<0) //<2>
x=x%d+d;
else
x=x%d;
printf("%lld\n",x);
}
return 0;
}
查看12道真题和解析
海康威视公司福利 1065人发布