取余运算的性质

同余式

image-20240218145611715

性质

逆元:a⋅b≡1(mod p)称a是b的乘法逆元，逆元: a·b ≡ 1 (mod~p) \\ 称a是b的乘法逆元，

image-20240218152823207

那如何计算逆元呢？使用快速幂算法就可以了

int qpow(int a,int n,int p) {
    int ans = 1;
    while(n) {
        if(n & 1 == 1) {
            ans = (ans*a) % p;
        }
       n>>1;
        a = (a*a) % p;
    }
    return ans;
}
int qpow2(int a,int n,int p) {
    if(n == 0) return 1;
    else if(n % 2 == 1) {
        return qpow2(a,n-1,p) % p;
    }else {
        int temp = qpow(a,n/2);
        return temp * temp % p;
    }
}
int inv(int a,int p) {
    return qpow(a,p - 2,p); //计算a^(p-2) %p 的值
}

同余方程

image-20240218145637571

x≡2(mod 9)x=9k+2(k=0,1,2,3,4...)x ≡ 2 (mod~9) \\ x = 9k + 2 (k = 0,1,2,3,4...) \\

一元同余方程组

image-20240218153535538

互质： gcd(a,b) = 1

image-20240218153727987

解为: x = 23

中国剩余定理

https://oi-wiki.org/math/number-theory/crt/

image-20240218155716356

image-20240218155833410

拿上面的来举例，我们来看看通解是怎么得出来的

image-20240218155900143

扩展欧几里得定理

https://zh.wikipedia.org/wiki/扩展欧几里得算法

扩展欧几里得算法（英语：Extended Euclidean algorithm）是欧几里得算法（又叫辗转相除法）的扩展。已知整数a、b，扩展欧几里得算法可以在求得a、b的最大公约数的同时，找到整数x、y（其中一个可能是负数），使它们满足贝祖等式

ax+by=gcd(a,b)ax + by = gcd(a,b)

扩展欧几里得算法C++实现：

#include <bits/stdc++.h>
using namespace std;

int ext_euc(int a, int b, int &x, int &y)
{
    if (b == 0)
    {
        x = 1, y = 0;
        return a;
    }

    int d = ext_euc(b, a % b, y, x);
    y -= a / b * x;

    return d;
}

int main()
{
    int a, b, x, y;
    cin >> a >> b;

    ext_euc(a, b, x, y);
    cout << x << ' ' << y << endl;
    return 0;
}

https://www.acwing.com/problem/content/879/

image-20240218160316186

#include <iostream>
using namespace std;

// 扩展欧几里得算法函数
// 参数：
//   a, b: 需要计算扩展GCD的整数
//   x, y: 引用参数，用于存储系数，使得 ax + by = gcd(a, b)
// 返回：
//   gcd(a, b)
int ext_gcd(int a, int b, int &x, int &y) {
    // 基本情况：当 b 等于 0 时，GCD 是 a，系数 x 和 y 分别为 1 和 0
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }

    // 递归调用，参数交换，系数 x 和 y 交换
    int d = ext_gcd(b, a % b, y, x);

    // 使用公式更新 y：y = y - (a/b) * x
    y -= a / b * x;

    // 返回最大公约数
    return d;
}

int main() {
    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
        int a, b, x, y;
        cin >> a >> b;

        // 调用扩展欧几里得算法函数
        int gcd = ext_gcd(a, b, x, y);

        // 输出方程 ax + by = gcd(a, b) 的系数 x 和 y
        cout << x << " " << y << endl;
    }

    return 0;
}

同余方程题

https://www.acwing.com/problem/content/205/

image-20240218162946513

#include <iostream>
using namespace std;
typedef long long ll;
ll ext_gcd(ll a,ll b,ll &x,ll &y) { //扩展欧几里得定理
    if(b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    ll d = ext_gcd(b,a%b,y,x);
    y = y - (a/b)*x;
    return d;
}
int main() {
    ll a,b,x,y;
    cin >> a >> b;
      ext_gcd(a,b,x,y);
      cout << (x%b + b)%b << endl;
}