【算法】数论基础小结

发布于 / 笔记 / 0 条评论

数论是纯粹数学的分支之一,主要研究整数的性质。被誉为“最纯”的数学领域。

总结了一些在寒假集训的时候学到的数论知识,不按难度排序。

关于素数

素数,指除了1和它本身没有其他因数的正整数。

朴素素数判定

即从定义出发,遍历从2到根号n所有数。如果存在一个数字是他的因数,则这个数不是素数。

实现代码如下:

bool checkPrime(int n)
{
    if (n < 2) return false;
    for (int i = 2; i < sqrt(n); i++)
    {
        if (n % i == 0) return false;
    }
    return true;
}

这种方法太过朴实,一般情况下不会用到。时间复杂度O(√n)

埃氏素数筛法

一种较为高效的判断素数的方法。能够一次性地筛选出某个区间的素数。

其中心思想是:如果某个数x是a的倍数,那么x一定不是素数。每次得到一个素数,则把他在这个区间内的所有素数都标记为合数。

实现代码如下:

const int MAXN = 1e4 + 5;
bool notPrime[MAXN];
void checkPrimeTo(int uplimit)
{
    notPrime[0] = notPrime[1] = 1;
    for (int i = 2; i <= uplimit; i++)
    {
        if (!notPrime[i])
        {
            for (int j = 2 * i; j <= uplimit; j += i)
            {
                notPrime[j] = 1;
            }
        }
    }
}

notPrime[n] == 1则表示n不是素数。这个算法看似是O(n ^ 2)的复杂度,其实随着i的不断增大,j的循环范围在不断变小。在整个测试的范围内,可以近似于线性复杂度。实际时间复杂度为O(nloglog(n))

线性欧拉筛法

在埃氏筛法的基础上,通过巧妙地限制每次筛去的数字数量,保证了每个合数只会被它的最小质因数筛去,因此每个数只会被标记一次。

实现代码如下:

const int MAXN = 1e7 + 5;
int notPrime[MAXN], primes[MAXN], top = 0;
void checkPrimeTo(int uplimit)
{
    notPrime[0] = notPrime[1] = 1;
    for (int i = 2; i <= uplimit; i++)
    {
        if (!notPrime[i]) primes[top++] = i;
        for (int j = 0; j < top; j++)
        {
            if (i * primes[j] > uplimit) break;
            check[i * primes[j]] = 1;
            if (i % primes[j] == 0) break;
        }
    }
}

primes[]记录的是筛出的素数们,通过遍记录素数,来保证每个数只会被便利一次。时间复杂度O(n)

Miller-Rabin素性测试

首先需要了解费马小定理

对于素数 p 和任意整数 a ,若gcd(a, p) == 1,
则有 a ^ p ≡ a (mod p),
即 a ^ (p - 1) ≡ 1 (mod p)。

那么,是否可以反过来利用这个定理来判断素数呢?基本可以。

但是有一类合数,用任何小于他们的质数为底进行判定,都满足这个定理。这种合数叫做伪素数,最小的伪素数是341。为了排除伪素数,我们引入了二次探测定理

对于素数 p ,则 x ^ 2 ≡ 1 (mod p) => ( x == 1 || x == p - 1 )

则对于a ^ (x - 1) = 1 (mod p)成立,若x - 1是奇数,则不再继续判断。否则继续判断是否a ^ ((x - 1) / 2) = 1 或 -1 (mod p)成立。如果不等于1或者-1则返回false,如果等于-1则返回true,如果等于1则继续向下判断。

选择前7个素数作为a,在[2, 1e18]内也就只有两三个可以通过Miller-Rabin测试的强伪素数了。

实现代码:(q_exp()为快速幂,q_mul()为快速乘)

typedef unsigned long long ll;
const int TIMES = 20; // 测试轮数

ll q_exp(ll a, ll k, ll mod)
{
	if (!k) return 1;
	ll ans = 1;
	while (k)
	{
		if (k & 1) ans = ans * a % mod;
		a = a * a % mod; k >>= 1;
	}
	return ans;
}
ll q_mul(ll a, ll b, ll mod)
{
	if (!b) return 0;
	ll ans = 0;
	while (b)
	{
		if (b & 1) ans = (ans + a) % mod;
		a = (a + a) % mod; b >>= 1;
	}
	return ans;
}

inline ll random(ll n)
{
    return ((double)rand() / RAND_MAX * n + 0.5); // RAND_MAX 定义于头文件
}

bool witness(ll a, ll n) // 二次探测
{
    ll tem = n - 1;
    int j = 0;
    while (!(tem & 1))
    {
        tem /= 2; j++;
    }

    ll x = q_exp(a, tem, n);
    if (x == 1 || x == n - 1) return true;
    
    while (j--)
    {
        x = q_mul(x, x, n);
        if (x == n - 1) return true;
    }
    
    return false;
}

bool miller_rabin(ll p) // 随机生成a来二次探测
{
    if (p == 2) return true;
    if (p < 2 || !(p & 1)) return true; // 剪枝
    
    for (int i = 1; i < TIMES; i++)
    {
        ll a = random(p - 1) + 1;
        if (!witness(a, p))
        {
            return false;
        }
    }
    return true;
}

int main()
{
    ll n; cin>>n;
    miller_rabin(n)? puts("It's a prime."): puts("It's not a prime");
}

Miller-Rabin的时间主要花在了计算a ^ (p - 1) mod p上,总体时间复杂度是O(logn)

关于最大公因数

对于最大的整数n,使得n同时是a和b的因子,则称n是a和b的最大公因数(Greatest common divisor)。

性质:gcd(a, b) * lcm(a, b) = a * b

递归求gcd

辗转相除法,直接上代码:

typedef long long ll;
inline ll gcd(int a, int b)
{
    return b? gcd(b, a % b): a;
}

扩展欧几里德算法(exgcd)

扩展欧几里德算法是用来解决已知a, b求解一组x, y,使它们满足: ax + by = gcd(a, b) = d的算法。

代码(接上部分代码):

ll exgcd(ll a, ll b, ll &x, ll &y)
{
    if (!b)
    {
        x = 1; y = 0; return a;
    }
    ll r = exgcd(b, a % b, x, y);
    ll tem = y;
    y = x - a / b * y;
    x = tem;
    return r;
}

关于组合数

组合数的定义

杨辉三角求组合数

根据推论:

C(m, n) = C(m, n - 1) + C(m - 1, n - 1)

可以预处理打表一个杨辉三角来求组合数。

代码大致为:

typedef long long ll;
const int MAXN = 1e4 + 5;
ll c[MAXN][MAXN];
void getC(int uplimit)
{
    c[0][0] = c[1][0] = c[1][1] = 1;
    for (int i = 2; i <= uplimit; i++)
    {
        c[i][0] = 1;
        for (int j = 1; j <= i; i++)
        {
            c[i][j] = c[i][j - 1] + c[i - 1][j - 1];
        }
    }
}

没啥注意的要点,时间复杂度O(n ^ 2)

逆元打表求组合数

步骤大概如下:

  1. 打表出1! ~ n!O(n)
  2. 求每个阶乘的逆元 – O(nlogn)
  3. 直接得:C(m, n) = n! / (m! * (n - m)!)O(1)

总体复杂度是O(nlogn)

Lucas定理

在数论中,Lucas定理用于计算二项式系数(m, n)被质数 p 除的所得的余数。

定理内容:对于非负整数 m 和 n 以及素数 p ,同余式:

(m, n) ≡ Π(i = 0 -> k) (m[i], n[i]) (mod p)

其中,m[i]n[i]mn 的 p 进制展开,当m < n 时,二项式系数(m, n) = 0

以后我学会Latex之后可能会重新写一下这里……这样平摊有点抽象_(:3。

这个方法使用递归,用于n和m巨大,但是p不太大且p为质数的时候。可直接求得:

C(m, n) ≡ C(m % p, n % p) * C(m / p, n / p)

代码就不写了。

分块打表求组合数

玄学操作,大概知道有这么一种方法就可以了。时间复杂度O(玄学)

零散的知识点

唯一分解定理

任何一个大于1的自然数 N,如果N不为质数,那么N可以唯一分解成有限个质数的乘积N = P1 ^ a1 * P2 ^ a2 * P3 ^ a3 ... Pn ^ an,这里P1 < P2 < P3 <...< Pn且均为质数,其中指数ai是正整数。这样的分解称为 N 的标准分解式。

同余定理

加减乘同余

模意义下,加减乘都不变,即:

(a % c + b % c) % c == (a + b) % c

减法、乘法同理。

逆元同余

逆元:

任意 x ∈ (1, p - 1),存在 y 使 x * y % p == 1,称 y 是 x 在 mod p 意义下的逆元

则:

(a % c) / (x % c) != (a / x) % c 

但是

(a % c) * (y % c) % c == (a / x) % c

欧拉函数/欧拉降幂

略(逃)

以上就是寒假集训中学到的一些数论知识点。

转载原创文章请注明,转载自: 冻葱Tewi » 【算法】数论基础小结

Not Comment Found