同余

Skyzhou666 · 2022-08-04 21:46:43 · 算法·理论

同余方程

同余基本法则：

欧几里得算法（辗转相除法）

最最最基础，四行搞定

int gcd(int a, int b)
{
    if(!b) return a;
    else return gcd(b, a % b);
}

扩展欧几里得算法

扩展欧几里得算法可以在求得a、b的最大公约数的同时，能找到整数x、y（其中一个很可能是负数），使它们满足贝祖等式：

ax + by = gcd(a, b)

模板如下，其中x和y用了&取地址是因为这个参数是要即时改变的，也可以用全局变量，不过为了背模板方便还是用&

void exgcd(int a, int b, int &x, int &y)
{
    if(!b) x = 1, y = 0;
    else exgcd(b, a % b, y, x), y -= a / b * x;
}

跑完这个函数后的x，y就是我们需要的整数解，但不一定是最小正整数解！需要的话还要加上答案处理。

扩欧解不定方程

形如ax+by=c的不定方程可以用扩欧来求

#include <iostream>
using namespace std;

int gcd(int a, int b)
{
    if(!b) return a;
    else return gcd(b, a % b);
}

void exgcd(int a, int b, int &x, int &y)
{
    if(!b) x = 1, y = 0;
    else exgcd(b, a % b, y, x), y -= a / b * x;
}

int main()
{
    int a, b, c;
    cin >> a >> b >> c;
    int g = gcd(a, b);
    if(c % g != 0)
    {
        cout << "Impossible!" << endl;
        return 0;
    }
    cout << g << endl;
    int x, y;
    exgcd(a, b, x, y);
    x *= c / g, y *= c / g;
    cout << "Any: " << x << " " << y << endl;
    int d = b / g;
    x = ((x % d) + d) % d;
    cout << "Mini Natural x: " << x << endl;
    return 0;
}

同余与扩欧的关系

求同余方程

ax\equiv p(mod\ n)

关于x的解，即ax与p模b同余，可以转化为

再转化为 $ax+by=p

现在转化成了不定方程通式，接下来就是将其转化成扩欧的形式，利用的就是以下两个定理：

1. 如果a和b都是整数，则有整数x和整数y使得ax+by=gcd(a,b)
2. a,b,p都是整数。

如果p不是gcd(a,b)的倍数，则此不定方程没有整数解。
如果p是其倍数，则有无穷多的解。
如果(x_0, y_0)是不定方程的一个解，那么其所有整数解为： x=x_0+k(\frac{b}{gcd(a,b)}) y=y_0-k(\frac{a}{gcd(a,b)})

那么就和我们的能用扩欧求解的方程十分相似，可以直接套模板。

逆元

在数学上讲，数a的逆元就是\frac{1}{a}，即与a相乘等于1的数。

在取模运算里面，对于整数a，当与a互质的模数b，当整数x满足ax\equiv 1(mod\ b)时，我们称x为a关于模b的逆元。

对于\frac{a}{b}\ mod\ p，实际上是不等于\frac{a\ mod\ p}{a\ mod\ p}的（详见最上面同余基本法则），所以要用到逆元。设x为a的逆元，则\frac{a}{b}\ mod\ p = a * x\ mod\ p。

那么由费马小定理知：

a\ mod\ p意义下的逆元就是a^{p-2}。

接下来一个快速幂就搞定了（

非常简洁的线性求逆元：

inv[1] = 1;
for(long long x = 2; x <= n; x++) inv[x] = (inv[m % x] * (m-m/x)) % m;

用O(n)的时间求出了1到n对模m的逆元！

中国剩余定理

#include <iostream>
#include <cmath>
#define MAXN 101
using namespace std;

void exgcd(long long a, long long b, long long &x, long long &y)
{
    if(!b) x = 1, y = 0;
    else exgcd(b, a % b, y, x), y -= a / b * x;
}

long long a[MAXN], b[MAXN];

int main()
{
    long long n, N = 1, ans = 0;
    cin >> n;
    for(long long x = 0; x < n; x++)
    {
        cin >> a[x] >> b[x];
        N *= a[x];
    }
    for(long long x = 0; x < n; x++)
    {
        long long m = N / a[x];
        long long ny, tmp;
        exgcd(m, a[x], ny, tmp);
        ans = (ans + m * (ny < 0 ? ny + a[x] : ny) * b[x]) % N;
    }
    cout << ans << endl;
    return 0;
}

2022.8.7：为什么扩欧被P3811乘法逆元模板卡常了啊啊啊啊

同余