裴蜀定理与扩展欧几里得算法

这篇是刷数论题时记的笔记。有一阵子遇到“求最小正整数差值”之类的题，我怎么也想不通它跟 gcd 有什么关系，直到把裴蜀定理和扩展欧几里得捋顺，回头看才发现全是套路。下面整理一下。

裴蜀定理

定理内容

如果(a)和(b)是不全为零的整数，则有整数(x, y)，使得(ax + by = gcd(a, b))

重要理解

等号右边也是随意给定整数(x, y)，能得到的最小正整数差值。

裴蜀定理推论

1. 如果(a)和(b)是不全为零的整数，且互质，当且仅当存在整数(x, y)，使得(ax + by = 1)
2. 如果(a)和(b)是不全为零的整数，并且(ax + by = c)有解，那么(c)一定是(gcd(a, b))的整数倍
3. 裴蜀定理可以推广到多项
   如果(ax + by = c)有解，就意味着一定有无穷多组解

扩展欧几里得算法

算法内容

对于方程(ax + by = gcd(a, b))，当(a, b)确定时，那么(gcd(a, b))也确定，（要保证入参(a)和(b)没有负数），扩展欧几里得算法可以给出(gcd(a, b))（用(d)表示）、以及其中一个特解(x, y)

时间复杂度

(O(log^3 min(a, b)))

求逆元

1. 费马小定理求逆元，要求满足模数必须为质数
2. 扩展欧几里得求逆元，不要求模数为质数，但是要求(a, b)互质
3. 一定要注意得到的(x)需要进行转化，保证一定为最小正整数。x = (x % mod + mod) % mod。我当时就在这栽过跟头，直接输出负数就 WA 了。

算法模板

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;
}

题目

P4549 【模板】裴蜀定理

思路

根据裴蜀定理的重要理解，题目所说的最小的正整数差值，就是这(n)个数的最大公约数。

示例代码

#include<bits/stdc++.h>

using namespace std;

#define ll long long
//#define int ll
#define pii pair<int, int>
#define all(x) x.begin(),x.end()
#define fer(i, m, n) for(int i = m; i < n; ++i)
#define ferd(i, m, n) for(int i = m; i >= n; --i)
#define dbg(x) cout << #x << ' ' << char(61) << ' ' << x << '\n'

const int MOD = 1e9 + 7;
const int N = 2e5 + 2;
const int inf = 1e9;

int gcd(int a, int b){
    return b ? gcd(b, a % b) : a;
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);

    int n, a;
    cin >> n;
    int ans = 0;
    while(n--) {
        cin >> a;
        ans = abs(gcd(ans, a));
    }
    cout << ans << '\n';
    return 0;
}

Pagodas 宝塔

思路

题意是说有(n)座宝塔，已经选了(a)和(b)两座，两人依次可以选第(ka + mb)座宝塔，也就是(a, b)的线性组合，实际上也就是裴蜀定理的左半部分。如果要使这个线性组合的式子如果为合法的数，那么这个数一定的(gcd(a, b))的整数倍，这样这个数才能被选择。那么计算有多少个这样的数即可。

示例代码

#include<bits/stdc++.h>

using namespace std;

#define ll long long
//#define int ll
#define pii pair<int, int>
#define all(x) x.begin(),x.end()
#define fer(i, m, n) for(int i = m; i < n; ++i)
#define ferd(i, m, n) for(int i = m; i >= n; --i)
#define dbg(x) cout << #x << ' ' << char(61) << ' ' << x << '\n'

const int MOD = 1e9 + 7;
const int N = 2e5 + 2;
const int inf = 1e9;

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);

    int t;
    cin >> t;
    fer(i, 1, t + 1) {
        cout << "Case #" << i << ": ";
        int n, a, b;
        cin >> n >> a >> b;
        int g = gcd(a, b);
        cout << (n / g & 1 ? "Yuwgna" : "Iaka") << '\n';
    }

    return 0;
}

Uniform Generator 均匀生成器

思路

从零开始，每次加(step)，因此就有(x \times step % mod = ?)这个(?)要取遍([0, mod - 1])内所有的数，也就是(x \times step + y \times mod = ?)而如果这个方程有解的话这个(?)一定是(gcd(step, mod))的整数倍，所以这个(gcd(step, mod) = 1)

示例代码

#include<iostream>
#include<iomanip>

using namespace std;

#define ll long long
//#define int ll
#define pii pair<int, int>
#define all(x) x.begin(),x.end()
#define fer(i, m, n) for(int i = m; i < n; ++i)
#define ferd(i, m, n) for(int i = m; i >= n; --i)
#define dbg(x) cout << #x << ' ' << char(61) << ' ' << x << '\n'

const int MOD = 1e9 + 7;
const int N = 2e5 + 2;
const int inf = 1e9;

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(0);

    int a, b;
    while(cin >> a >> b){
        cout << setw(10) << a << setw(10) << b << "    " << (gcd(a, b) == 1 ? "Good Choice" : "Bad Choice") << '\n';
        cout << "\n";
    }

    return 0;
}

P1082 [NOIP 2012 提高组] 同余方程

思路

题目说保证一定有解 => (a, b)互质。也就是求(a)在模(b)意义下的逆元，用扩展欧几里得算法求得的(x)即为答案。注意需要保证得到的(x)为最小正整数。

示例代码

#include<bits/stdc++.h>

using namespace std;

#define ll long long
//#define int ll
#define pii pair<int, int>
#define all(x) x.begin(),x.end()
#define fer(i, m, n) for(int i = m; i < n; ++i)
#define ferd(i, m, n) for(int i = m; i >= n; --i)
#define dbg(x) cout << #x << ' ' << char(61) << ' ' << x << '\n'

const int MOD = 1e9 + 7;
const int N = 2e5 + 2;
const int inf = 1e9;

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() {
    ios::sync_with_stdio(false); cin.tie(nullptr);

    int a, b;
    cin >> a >> b;
    int x, y;
    exgcd(a, b, x, y);
    cout << (x % b + b) % b << '\n';

    return 0;
}

P2054 [AHOI2005] 洗牌

思路

经过观察得出规律，第(x)张牌经过一次洗牌之后所在的位置更新为(2 \times x % (n + 1))。那么设题目要求的经过(m)次洗牌之后第(L)张牌上的数字是(x)，则有(x \times 2 ^ m % (n + 1) = L),
<=> (x \times 2 ^ m + y \times (n + 1) = L)。我们要解上述方程的(x)可以先解下面这个方程:(x1 \times 2 ^ m + y1 \times (n + 1) = 1)。因为(2 ^ m)一定是2的倍数也是偶数，(n + 1)是奇数，二者互质，方程一定有解。解出(x1)之后，只需再乘(L)即可。
注意：经过欧几里得求得的(x)不一定为最小正整数，因此需要对其进行处理

示例代码

#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define int ll
#define pii pair<int, int>
#define all(x) x.begin(),x.end()
#define fer(i, m, n) for(int i = m; i < n; ++i)
#define ferd(i, m, n) for(int i = m; i >= n; --i)
#define dbg(x) cout << #x << ' ' << char(61) << ' ' << x << '\n'

const int MOD = 1e9 + 7;
const int N = 2e5 + 2;
const int inf = 1e9;

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;
}

ll fmul(int a, int b, int mod){
    ll ans = 0;
    while(b){
        if(b & 1) ans = (ans + a) % mod;
        a = a * 2 % mod;
        b >>= 1;
    }
    return ans;
}

ll fpow(int a, int b, int mod){
    ll ans = 1;
    while(b){
        if(b & 1) ans = fmul(ans, a, mod);//注意应该用快速乘
        a = fmul(a, a, mod);// 注意应该用快速乘
        b >>= 1;
    }
    return ans;
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);

    ll n, m, l;
    cin >> n >> m >> l;
    // x * 2 ^ m % (n + 1) = L
    // x * 2 ^ m + y * (n + 1) = L
    // 先求 x1 * 2 ^ m + y1 * (n + 1) = 1(2 ^ m 为偶数，n + 1为奇数，并且一定互质)
    int x1, y1;
    exgcd(fpow(2, m, n + 1), n + 1, x1, y1);
    x1 = (x1 % (n + 1) + n + 1) % (n + 1);// 注意保证x1为正数
    cout << fmul(x1 % (n + 1), l, n + 1) << '\n';
    return 0;
}