扩展欧几里德算法

数论只会GCD

gcd的辗转相除法

实现:

1
2
3
4
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}

或者直接使用

1
2
3
#include <algorithm>

__gcd();

辗转相除法复杂度在O(logmax(a,b))O(\log \max(a, b))

扩展欧几里德算法

  • 先了解同余方程a×xb(modm)a\times x≡b(\mod m),该方程等价于a×x=b+m×ka\times x=b+m\times k
    可化为a×x+b×y=ca\times x+b\times y=c的形式
    先看"求整数x,y使a×x+b×y=1a\times x+b\times y=1",显然gcd(a,b)=1,才能保证有解。事实上,一定存在(x,y)使a×x+b×y=gcd(x,y)a\times x+b\times y=gcd(x,y)
  • 模板
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
ll extgcd(ll a, ll b, ll &x, ll &y)
{
ll d = a;
if (b != 0)
{
d = extgcd(b, a % b, y, x);
y -= (a / b) * x;
}
else
{
x = 1;
y = 0;
}
return d;
}

青蛙的约会

细想其实是道思维+extgcd的模板题
设t为跳跃次数
(nm)×txy(modL)(n-m)\times t≡x-y(\mod L)
所以(nm)×t+k×L=xy(n-m)\times t+ k\times L=x-y
nm=a,L=b,xy=cn - m = a,L = b,x - y = c
则化为ax+by=cax + by = c
又已知ax0+by0=gcd(a,b)ax_0+by_0=gcd(a,b)x0x_0是一个解
式子两边同乘cg\frac{c}{g}
得到acx0g+bcy0g=ca\frac{cx_0}{g}+b\frac{cy_0}{g}=c
x=cx0gx=\frac{cx_0}{g}就是ax+by=c的一个解

k是一个随机整数;gcd是gcd(a,b);则有公式
x=cx0gx0+(b/gcd)kx=\frac{cx_0}{g}x_0 + (b/gcd)k

y=cx0gy0(a/gcd)ky=\frac{cx_0}{g}y_0 - (a /gcd)k

把(b/gcd)k通过取余除去即可得到最小解,这里注意正负

1
2
3
4
5
x = x * c / gcd;
int t = b / gcd;
x = (x % t + t) % t;
//这一步+t%t是为了防止x为负数
printf("%lld\n", x);
  • AC代码
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
76
77
78
79
80
81
82
83
84
85
86
87
88
/*************************************************************************
> FileName:
> Author: Lance
> Mail: lancelot_hcs@qq.com
> Date: 9102.1.8
> Description:
************************************************************************/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <string>
#include <cmath>
#include <sstream>
using namespace std;
typedef long long ll;
const double pi = acos(-1.0);
const int eps = 1e-10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;//int2147483647//ll9e18//unsigned ll 1e19
const int maxn = 1005;
ll read()
{
ll x = 0,f = 1;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}

ll extgcd(ll a, ll b, ll &x, ll &y)
{
ll d = a;
if (b != 0)
{
d = extgcd(b, a % b, y, x);
y -= (a / b) * x;
}
else
{
x = 1;
y = 0;
}
return d;
}
ll a, b, c, x, y;

int main()
{
ll m, n, gcd, L;
while (~scanf("%lld%lld%lld%lld%lld", &x, &y, &m, &n, &L))
{
a = m - n;
b = L;
c = y - x;
if (a < 0)
{
a = -a;
c = -c;
}
gcd = extgcd(a, b, x, y);
if (c % gcd != 0)
puts("Impossible");
else
{
x = x * c / gcd;
int t = b / gcd;
x = (x % t + t) % t;
printf("%lld\n", x);
}
}
return 0;
}

参考大佬博客