基础数论笔记

发布于 2019-11-09  279 次阅读


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

本文的“%”符号除特殊声明外,均指模运算,即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的倍数,则有ap−1) ≡ 1(mod p

我们可以发现ap−1) ≡ 1(mod p可以变成a × ap − 2 ≡ 1(mod p)

所以ap − 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];
}