0%

exgcd


题目链接: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;
}
谢谢你,秋刀鱼今天有吃的了!!!