基础数论笔记

注意，本文不适合初学者阅读。适合有一定基础的盆友。

本文的“%”符号除特殊声明外，均指模运算，即mod

欧几里得算法（gcd）

辗转相除法，用于求两个数的最大公约数。

公式：

gcd (a,b) = gcd(b,a % b)

当a mod b = 0时，b便为我们要找的最大公约数

代码：

int gcd(int a, int b)
{
    if(b == 0) return a;
    return gcd(b, a % b);
}

最小公倍数(lcm)

公式：

a × b ÷ gcd(a, b)

扩展欧几里得算法（exgcd）

exgcd可以做以下事情：

1. 求解类似ax × by = gcd(a,b)的一组可行解。
2. 求逆元
3. 求线性同余方程组的一组可行解。

是不是很强大呢

代码：

int exgcd(int a, int b, int &x ,int &y)
{
    if(b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    int ans = exgcd(b, b % a); //顺便求gcd(a,b)的值   
    int tx = x;
    x = y;
    y = tx - a / b * y;
    return ans;
}

求解线性同余方程

形如这样的东东名叫线性同余方程：

ax ≡ c (mod b)

这个方程组等价于ax + by = c，它有整数解的充要条件为c % gcd(a, b) = 0。

我们可以用exgcd来求解。

我们先用exgcd求出ax + by = gcd(a, b)的一组解，之后等式两边同除gcd(a, b)再乘上c，等式变成了：ax ÷ gcd(a, b) × c + bx ÷ gcd(a, b) × c = c，于是我们便求出了一组解。

代码：

int exgcd(int a, int b, int &x, int &y)
{
    if (b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    int ans = exgcd(b, b % a);
    int tx = x;
    x = y;
    y = tx - a / b * y;
    return ans;
}

void work(int a, int b, int c, int &x, int &y)
{
    int d = exgcd(a, b, x, y);
    if (c % d)
        cout << "无整数解";
    else
    {
        int k = c / d;
        x *= k;
        y *= k;
    }
}

关于求出的解是负数

我们可以把答案不停的加上模数，直到它为正数为止，输出时候再取个模。

逆元

逆元是一类特殊的线性同余方程，形如ax ≡ 1(mod b)且a和b互质，则称x是a在模b意义下的逆元，记作a^− 1。具体解法和求解线性同余方程基本一样，不再放代码了。

介绍一下费马小定理求逆元和线性递推。

费马小定理

以下内容来自百度百科。

费马小定理(Fermat's little theorem)是数论中的一个重要定理，在1636年提出。如果p是一个质数，而整数a不是p的倍数，则有a^（p−1） ≡ 1（mod p）

我们可以发现a^（p−1） ≡ 1（mod p）可以变成a × a^p − 2 ≡ 1(mod p)。

所以a^p − 2便是答案。

线性递推求逆元

直接放代码(不太常用)：

a[i] = -(p/i) * a[p % i];

卡特兰数

公式

$$\sum_{i = 1}^{n}{f_{i - 1}f_{n - i}}$$

代码：

f[0] = 1, f[1] = 1;
for (register int i = 2; i <= n; i++)
{
for (register int j = 0; j < i; j++)
f[i] += f[j] * f[i - j - 1];
}