数论

发表于 2022-07-13 分类于信奥，数学阅读次数：

最简单的数论。

1. 质数

判断质数

\(O(1)\) 判断方法

bool is_prime[110] = {0,0,1,1,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0};

bool check_prime(int n) {
	return is_prime[n];
}

这里附上 \(1000\) 以内的数组内容：

bool is_prime[1010] = {0,0,1,1,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0};

以及生成 \(bool\) 表的标程：

//改变maxn即可
#include <iostream>
using namespace std;

const int maxn = 1000;

int main() {
	freopen("a.txt","w",stdout);
	cout << "bool is_prime[" << maxn + 10 << "] = {";
	cout << "0,0";
	for(int i = 2; i <= maxn; i++) {
		bool is_prime = true;
		for(int j = 2; j * j <= i; j++) {
			if (i % j == 0) {
				is_prime = false;
			}
		}	
		cout << ',' << is_prime;
	}
	cout << "};" << endl;
	fclose(stdout);
	return 0;
}

\(O(\sqrt{n})\) 判断方法

//注意 n <= 1 时的特判和 i * i 的优化
bool check_prime(int n) {
	if (n <= 1) return false;
    bool is_prime = true;
	for(int i = 2; i * i <= n; i++) {
    	if (n % i == 0) {
            is_prime = false;
            break;
        }
    }
    return is_prime;
}

质数表

利用定义循环求质数 \(O(n\sqrt{n})\)

//sqrt(maxn)优化
vector<int> primes;

void get_prime(int maxn) {
    primes.clear();
    if (maxn <= 1) {
        return;
    }
    for(int i = 2; i <= maxn; i++) {
        bool is_prime = true;
        for(int j = 2; j * j <= i; j++) {
            if (i % j == 0) {
                is_prime = false;
                break;
            }
        }
        if (is_prime) {
            primes.push_back(i);
        }
    }
    return;
}

优化 \(O(pn)\) （p为n以内质数个数）

每次只要除质数即可，除以合数是没有意义的。

vector<int> primes;

void get_prime(int maxn) {
    primes.clear();
    if (maxn <= 1) {
        return;
    }
    primes.push_back(2);
    for(int i = 3; i <= maxn; i++) {
        bool is_prime = true;
        for(int j = 0; j < primes.size() && primes[j] * primes[j] <= i; j++) {
            if (i % primes[j] == 0) {
                is_prime = false;
                break;
            }
        }
        if (is_prime) {
            primes.push_back(i);
        }
    }
    return;
}

当 \(maxn\) 很大时，时间复杂度接近常数

筛法求质数

常见的算法有埃氏筛和欧拉筛。由于欧拉筛算法更快，接近 \(O(n)\) ，一般都用欧拉筛。

vector<int> primes;

void get_prime(int maxn) {
    bool *np = new bool[maxn];
    for (int i = 2; i <= maxn; i++) {
        if (!np[i]) primes.push_back(i);
        for (int j = 0; j < primes.size() && primes[j] * i <= n; j++) {
            np[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
    delete[] np;
}

筛法求其它积性函数

以求欧拉函数为例：

vector<int> primes;
int phi[maxn];

void get_phi(int maxn) {
    bool *np = new bool[maxn];
    for (int i = 2; i <= maxn; i++) {
        if (!np[i]) {
            primes.push_back(i);
            phi[i] = i - 1;
        }
        for (int j = 0; j < primes.size() && primes[j] * i <= n; j++) {
            np[primes[j] * i] = true;
            if (i % primes[j] == 0) {
                phi[i * primes[j]] = phi[i] * primes[j];
                break;
            }
            phi[i * primes[j]] = phi[i] * phi[primes[j]];
        }
    }
    delete[] np;
}

2. 最大公因数

定义

最大公因数，也称最大公约数、最大公因子，指两个或多个整数共有约数中最大的一个。 \(a,b\) 的最大公约数记为 \((a,b)\) ，同样的， \(a,b,c\) 的最大公约数记为 \((a,b,c)\) ，多个整数的最大公约数也有同样的记号。求最大公约数有多种方法，常见的有质因数分解法、短除法、辗转相除法、更相减损法。与最大公约数相对应的概念是最小公倍数， \(a,b\) 的最小公倍数记为 \([a,b]\) 。

求法

递归写法（辗转相除）

1
2
3

int gcd(int x,int y) {
	return y == 0 ? x : gcd(y, x % y);
}

STL写法（~~我懒得看源码~~）

1
2
3

int gcd(int x,int y) {
	return __gcd(x, y);
}

Cms的奇怪的位运算（谁看得懂私我）

int gcd(int x,int y) {
	while(y ^= x ^= y ^= x %= y);
	return x;
}

最小公倍数

~~定义被鸽了~~

前置芝士

\[\forall a,b \in N , ab = (a,b) \cdot [a,b]\]

用自然语言描述就是：两个自然数的最大公约数与它们的最小公倍数的乘积等于这两个数的乘积。

证明如下：

设 \(k = (a,b)\) , 则 \(a = ka_0,b = kb_0\) ，且 \((a_0,b_0) = 1,[a_0,b_0] = a_0b_0\) 。

\(\Rightarrow [a,b] = [a_0k,b_0k] = [a_0,b_0]k = a_0b_0k = \frac{ab}{k}\)

\(\Rightarrow (a,b) \cdot [a,b] = ab\)

证毕

求最小公倍数

1
2
3

int lcm(int x,int y) {
    return a * b / gcd(a,b);
}

3. 扩展欧几里得算法

欧几里得算法

~~谁是欧几里得？自己百度去。~~

先看看什么是欧几里得算法：

\[\forall a,b \in Z, (a,b) = (b,a \% b)\]

所以 \(gcd\) 就可以用之前提到的方法算：

1
2
3

int gcd(int x, int y) {
	return y == 0 ? x : gcd(y, x % y);
}

扩展

扩展欧几里得可以用来求一个关于裴蜀定理的方程：

\[ax + by = (a,b)\]

裴蜀定理：

若 \(a,b\) 是整数,且 \((a,b) = d\) 那么对于任意的整数 \(x,y\) , \(ax+by\) 都一定是 \(d\) 的倍数，特别地，一定存在整数 \(x,y\) ，使 \(ax + by = d\) 成立。

我们先来看看扩欧怎么写：

在欧几里得算法里，递归部分的核心是这样的： \((a,b) = (b,a \% b) = (b,a - b \lfloor \frac {a}{b}\rfloor)\) ，我们将由此得出与 \(x,y\) 相关的递归关系。

根据裴蜀定理，我们可以找到四个整数 \(x,y,x',y'\) ，使得 \(ax + by = (a,b)\) 且 \(bx' + (a - b \lfloor \frac {a}{b}\rfloor)y' = (b,a - b \lfloor \frac {a}{b}\rfloor)\) 。

这两个等式的右侧是相等的，于是我们得到： \(ax + by = bx' + (a - b \lfloor \frac {a}{b}\rfloor)y'\) ，整理一下就是 \(a(x - y') + b(y - (x' - \lfloor \frac {a}{b} \rfloor y')) = 0\) 。

我们希望这个等式对一切 a，b 都成立，于是 \(x = y'\) 且 \(y = x' - \lfloor \frac {a}{b} \rfloor y'\) 。

这样，要求解 \(x\) 和 \(y\)，只需要求解 \(x'\) ， \(y'\) ，由于 \(x'\) ， \(y'\) 对应的问题规模更小，所以可以进行递归的运算。最后找一下边界条件：当 \(b = 0\) 时， \((a,0)\) 对应 \(x = 1\) ， \(y = 0\) 。

这种算法的思想和欧几里得算法是一致的，而且它在求出最大公约数的同时，求解了一组适于裴蜀定理的系数，所以叫做扩展欧几里得算法。

实现：

int ex_gcd(int a,int b,long long &x,long long &y) {
	if (b == 0) {
    	x = 1;
        y = 0;
        return a;
    }
    int d = ex_gcd(b,a % b,y,x);
    y -= a / b * x;
    return d;
}

当然 \(ex\_gcd\) 不可能只有这么点用途，它还可以用来求逆元。

逆元：

如果 \(a * b \equiv 1 \pmod m\) ，那么 \(a,b\) 互为逆元。

当题目要求对结果求 \(mod\) 的模，且当过程需要计算 \(a/b\) 时，需要对 \(a/b\) 取模，即 \((a/b)\ \% \ m\) ，但是余数不具有可除性，所以要变除法为乘法。

此时，设 \(c\) 是 \(b\) 的逆元

则：\(b * c \equiv 1\pmod m\)

\(\therefore (a/b) \ \% \ m = (a/b) * 1\ \% \ m = (a/b) * b * c \ \% \ m = (a * c) \ \% \ m\)

\(\therefore (a/b) \ \% \ m = (a\ \%\ m * c \ \%\ m)\ \%\ m\)

这样就把除法变成乘法了。

设 \(x\) 为 \(a\) 在模 \(p\) 意义下的逆元，那么满足式子：

\(ax \equiv 1 \pmod m\)

那么有：

\(ax+my=1\)

然后用 \(ex\_gcd\) 求出 \(x\) 即可。

求法：

long long inv(long long a,long long m) {
    long long x,y;
    long long d = ex_gcd(a,m,x,y);
    return d == 1 ? (x + m) % m : -1; //不互质则没有逆元
}