题目链接:VJ(private)
扩展欧几里得定理
青蛙的约会 题目描述 两只青蛙在网上相识了,它们聊得很开心,于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上,于是它们约定各自朝西跳,直到碰面为止。可是它们出发之前忘记了一件很重要的事情,既没有问清楚对方的特征,也没有约定见面的具体位置。不过青蛙们都是很乐观的,它们觉得只要一直朝着某个方向跳下去,总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上,不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙,你被要求写一个程序来判断这两只青蛙是否能够碰面,会在什么时候碰面。 我们把这两只青蛙分别叫做青蛙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
解释 可以列出同余方程 (x + m * t) % l = (y + n * t) % l,即(x + m * t) = (y + n * t) + k * l。移项得(x - y) + t * (m - n) = k * l。仿照二元一次不定方程的形式ax + by = c,我们可以得到l * k + (n - m) * t = x - y。 根据输入的数据,我们知道l, m, n, x, y这五个数,并且可以求出(n - m)和(x - y)。我们将l, (n - m), (x - y)代入扩展欧几里得算法, 得到k和t的一组解(x0 * (c / gcd(a, b)), y0 * (c / gcd(a, b)))。 方程无解的条件是c % gcd(a, b) != 0。如果满足方程无解的条件,输出”Impossible”。 否则,我们要求的是t的最小非负整数解。 t的公式可以通过(y0 + a / gcd(a, b)) % (a / gcd(a, b))得到。 (上述部分为了解释更清楚,和代码部分的字母有所不同。)
代码部分 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 #include <iostream> #define int long long using namespace std;int exgcd (int a,int b,int &x,int &y) { if (!b) { x=1 ,y=0 ; return a; } int d=exgcd (b,a%b,y,x); y-=a/b*x; return d; } signed main () { int x0,y0,m,n,l; cin>>x0>>y0>>m>>n>>l; int x,y; int r=exgcd (l,n-m,x,y); if ((x0-y0)%r!=0 ) cout<<"Impossible\n" ; else { int t=(y*(x0-y0)/r%(l/r)+l/r)%(l/r); cout<<t<<endl; } return 0 ; }
exgcd 题目描述 给出一个等式ax + by = c,计算可能的解(x0, y0)使得|x0 + y0|的值最小。 如果有多组解,输出其中的一种;如果无解,输出-1。
输入 t组数据,每组数据1行,包含a,b,c。其中-1e9 <= a,b,c <= 1e9, 1 <= T <= 1e5。
输出 同题目描述
样例输入 4 1 2 3 1 -1 -2 5 7 3 2 4 -3
样例输出 1 1 0 2 2 -1 -1
Note 在第二组数据中,(-1,1)也是一组可行解。
解释 首先判断a = 0,或者b = 0的一些情况,然后将a, b, c跑一次扩展欧几里得算法,得到一组解。我们要求的是绝对值之和最小的一组解。我的方法是:首先将x为最小非负整数的情况求出来,然后算出此时的y;然后将x为最大非正整数的情况求出来,算出此时的y;将y为最小非负整数的情况求出来,算出此时的x,将y为最大非正整数的情况求出来,算出此时的y。将这几种情况比较,就能得到最终绝对值之和最小的解。 不得不说,这题我的代码较为冗余丑陋。
代码部分 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 #include <iostream> #define int long long using namespace std;int exgcd (int a,int b,int &x,int &y) { if (!b) { x=1 ,y=0 ; return a; } int d=exgcd (b,a%b,y,x); y-=a/b*x; return d; } signed main () { int t; cin>>t; while (t--) { int a,b,c; cin>>a>>b>>c; if (a==0 &&b==0 ) { if (c==0 ) cout<<"0 0" <<endl; else cout<<-1 <<endl; continue ; } int x,y; int r=exgcd (a,b,x,y); if (c%r!=0 ) { cout<<-1 <<endl; continue ; } int x0=x*(c/r),y0=y*(c/r); pair<int ,int > res; res.first=1e9 +1 ,res.second=1e9 +1 ; if (a==0 ||b==0 ) { cout<<x0<<' ' <<y0<<endl; continue ; } int xx,yy,k; xx=(x0+(b/r))%(b/r); k=(xx-x0)/(b/r); yy=y0-(a/r)*k; if (abs (xx)+abs (yy)<=abs (res.first)+abs (res.second)) { res.first=xx,res.second=yy; } xx-=(b/r); yy+=(a/r); if (abs (xx)+abs (yy)<=abs (res.first)+abs (res.second)) { res.first=xx,res.second=yy; } xx+=(b/r),xx+=(b/r); yy-=(a/r),yy-=(a/r); if (abs (xx)+abs (yy)<=abs (res.first)+abs (res.second)) { res.first=xx,res.second=yy; } yy=(y0+(a/r))%(a/r); k=(y0-yy)/(a/r); xx=x0+(b/r)*k; if (abs (xx)+abs (yy)<=abs (res.first)+abs (res.second)) { res.first=xx,res.second=yy; } xx+=(b/r); yy-=(a/r); if (abs (xx)+abs (yy)<=abs (res.first)+abs (res.second)) { res.first=xx,res.second=yy; } xx-=(b/r),xx-=(b/r); yy+=(a/r),yy+=(a/r); if (abs (xx)+abs (yy)<=abs (res.first)+abs (res.second)) { res.first=xx,res.second=yy; } cout<<res.first<<' ' <<res.second<<endl; } return 0 ; }