扩展欧几里德算法

,
数论只会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(log⁡max⁡(a,b))O(\log \max(a, b))

扩展欧几里德算法

  • 先了解同余方程a×x≡b(mod  m)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为跳跃次数
(n−m)×t≡x−y(mod  L)(n-m)\times t≡x-y(\mod L)
所以(n−m)×t+k×L=x−y(n-m)\times t+ k\times L=x-y
令n−m=a,L=b,x−y=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;
}

参考大佬博客