Chapter 4

质数

试除法求质数

从 2 ~ sqrt(n) ，实际写成 i <= x / i
注意i 从 2 开始

分解质因数

每当碰到能整除(从二开始)就除尽，每除一次cnt ++

筛质数 (欧拉线性筛)

思路：每个数都用其最小质因数筛掉，从而保证每个数只被筛一次，故时间复杂度为 O(N)

#include <iostream>

using namespace std;

const int N = 1000010;

int primes[N], cnt;
bool st[N];

void get_primes(int n) {
	for (int i = 2; i <= n; i++) {
		if (!st[i]) primes[cnt++] = i;
		for (int j = 0; primes[j] <= n / i; j++) {
			st[i * primes[j]] = true;
            // 若 i % primes[j] 说明i * primes[j] 最小质因子是 primes[j] ，则往后的i * primes[k] 最小质因子仍是 primes[j] ，
            // 应交给后面的循环
			if (i % primes[j] == 0) break;
		}
	}
}

int main() {
	int n;
	cin >> n;

	get_primes(n);

	cout << cnt << endl;

	return 0;
}

约数

试除法求约数

思路：用vector存，每当碰到可整除的情况，将其将入，若i != x / i, x / i 也加入，排序后输出即可
循环范围： 2 ~ sqrt(n) 再单独检验 x > 1 则加入

约数个数
思路：分解质因数，为各个质因数指数加一的乘积

约数之和
思路：分解质因数，先对每个质因数求等比数列和，再将各个和相乘(将数组换成哈希表来存)

#include <iostream>
#include <unordered_map>

using namespace std;

const int mod = 1e9 + 7;

int main() {
	int n;
	cin >> n;

	unordered_map<int, int> primes;

	while (n--) {
		int x;
		cin >> x;
		for (int i = 2; i <= x / i; i++) {
			while (x % i == 0) {
				primes[i]++, x /= i;
			}
		}
		if (x > 1) primes[x]++;
	}

	long long res = 1;
	for (auto p : primes) {
		int a = p.first, b = p.second;
		long long t = 1;
		while (b--) {
			t = (t * a + 1) % mod;
		}
		res = res * t % mod;
	}

	cout << res << endl;

	return 0;
}

最大公约数
思路： return (b ? gcd(b , a % b) : a);

欧拉函数

定义法求欧拉函数

注意循环范围和求质因数相同，都是先2 ~ sqrt(n) ，再检验 x > 1 则也加入

#include <iostream>

using namespace std;

int phi(int x) {
	int res = x;
	for (int i = 2; i <= x / i; i++) {
		if (x % i == 0) {
			res = res / i * (i - 1);
			while (x % i == 0) x /= i;
		}
	}
	if (x > 1) res = res / x * (x - 1);

	return res;
}

int main() {
	int n;
	cin >> n;
	while (n--) {
		int x;
		cin >> x;
		cout << phi(x) << endl;
	}

	return 0;
}

线性筛求欧拉函数

思路：

若primes[j] 整除 i ，则质因数组成不变， euler[i * primes[j]] = euler[i] * primes[j]

否则，根据欧拉函数积性和 euler[质数p] = p - 1， euler[i * primes[j]] = euler[i] * (primes[j] - 1)

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1000010;

int primes[N], cnt;
int eulers[N];
bool st[N];

void get_eulers(int x) {
	eulers[1] = 1;
	for (int i = 2; i <= x; i++) {
		if (!st[i]) {
			eulers[i] = i - 1;
			primes[cnt++] = i;
		}

		for (int j = 0; i <= x / primes[j]; j++) {
			st[i * primes[j]] = true;
			if (i % primes[j] == 0) {
                // 同样，按照线性筛的框架，能整除时要记得break
				eulers[i * primes[j]] = eulers[i] * primes[j];
				break;
			}
			eulers[i * primes[j]] = eulers[i] * (primes[j] - 1);
		}
	}
}

int main() {
	int n;
	cin >> n;

	get_eulers(n);

	long long res = 0;
	for (int i = 1; i <= n; i++) res += eulers[i];

	cout << res << endl;

	return 0;
}

快速幂

模版

#include <iostream>

using namespace std;

typedef long long LL;

LL qmi(LL a, LL b, LL p) {
	LL res = 1 % p;
	while (b) {
		if (b & 1)	res = res * a % p;
		a = a * a % p;
		b >>= 1;
	}
	return res;
}

int main() {
	int n;
	cin >> n;
	while (n--) {
		LL a, b, p;
		cin >> a >> b >> p;
		cout << qmi(a, b, p) << endl;
	}

	return 0;
}

快速幂求逆元

思路：由欧拉定理，a 在模质数 p 意义下的逆元是 qmi(a, p - 2, p)

拓展欧几里得算法

模版

思路： by + (a - b(a/b))x = d ，变形得 ax + b*(y - a/b*x) = d 则由此得到符合要求的 y = y - a / b * x

#include <iostream>

using namespace std;

// x 和 y 要修改 ，故传引用 (a*x + b*y = gcd(a,b))
int exgcd(int a, int b, int& x, int& y) {
	if (!b) {
		x = 1, y = 0;
		return a;
	}

	int d = exgcd(b, a % b, y, x);
	y -= a / b * x;
	return d;
}

int main() {
	int n;
	cin >> n;

	while (n--) {
		int a, b;
		cin >> a >> b;

		int x, y;
		int d = exgcd(a, b, x, y);
		cout << x << " " << y << endl;
	}

	return 0;
}

线性同余方程

思路：简单代数变形即可，b是gcd(a,m) 等价于有解，最后输出结果时， x 要随之扩大为原先的 b/d 倍

#include <iostream>

using namespace std;

int exgcd(int a, int b, int& x, int& y) {
	if (!b) {
		x = 1, y = 0;
		return a;
	}

	int d = exgcd(b, a % b, y, x);
	y -= a / b * x;
	return d;
}

int main() {
	int n;
	cin >> n;

	while (n--) {
		int a, b, m;
		cin >> a >> b >> m;

		int x, y;
		int d = exgcd(a, m, x, y);

		if (b % d) cout << "impossible" << endl;
		else cout << (long long)b / d * x % m << endl;
	}

	return 0;
}

中国剩余定理

模版
思路：每次合并两个方程(均由 x 的两种表示方式而来)

#include <iostream>

using namespace std;

typedef long long LL;

LL exgcd(LL a, LL b, LL& x, LL& y) {
	if (!b) {
		x = 1, y = 0;
		return a;
	}

	LL d = exgcd(b, a % b, y, x);
	y -= a / b * x;
	return d;
}

int main() {
	int n;
	cin >> n;

	LL x = 0;

	LL a1, m1;
	cin >> a1 >> m1;
    // 合并只有 n - 1 次， 注意循环次数
	for (int i = 0; i < n - 1; i++) {
		LL a2, m2;
		cin >> a2 >> m2;

		LL k1, k2;
		int d = exgcd(a1, a2, k1, k2);

		// 无解
        if ((m2 - m1) % d) {
			x = -1;
			break;
		}

		// 合并方程，k1 作为新方程的 k 同步扩大
        k1 *= (m2 - m1) / d;
        // 变成mod (a2 / d) 意义下的， 由丢番图方程通解形式可知
		k1 = (k1 % (a2 / d) + a2 / d) % (a2 / d);

		// 更新 x 和 a1
        x = k1 * a1 + m1;
		m1 = k1 * a1 + m1;
        // 更新 a 为两个方程里 a 的最小公倍数 (二者之积除以最大公因数)
		a1 = abs(a1 / d * a2);
	}

	// 只剩最后一个方程时， 取 m1 在 0 ~ a1 范围内的代表元即可
    if (x != -1) cout << (m1 % a1 + a1) % a1 << endl;
	else cout << x << endl;

	return 0;
}

高斯消元法

模版

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>

using namespace std;

const int N = 110;
const double eps = 1e-8;

int n;
double a[N][N];

int gauss() {
	int r = 0, c = 0;
	// 注意以列为递增
	for (; c < n; c++) {
		int t = r;
		// 把当前列绝对值最大的一行找出来
		for (int i = r; i < n; i++) {
			if (fabs(a[i][c]) > fabs(a[t][c])) t = i;
		}

		// 若该列全0，直接跳过
		if (fabs(a[t][c]) < eps) continue;

		// 交换
		for (int i = c; i <= n; i++) swap(a[r][i], a[t][i]);
		// 行首元素化一(注意倒序，因为要用到a[r][c])
		for (int i = n; i >= c; i--) a[r][i] /= a[r][c];
		for (int i = r + 1; i < n; i++) {
			//当前列对应元素非零时才消元(同样注意倒序，因为要用到a[i][c])
			if (fabs(a[i][c]) > eps) {
				for (int j = n; j >= c; j--) a[i][j] -= a[i][c] * a[r][j];
			}
		}

		r++; // 满足条件时 r 才递增
	}

	if (r < n) {
		for (int i = r; i < n; i++) {
			if (fabs(a[i][n]) > eps) return 2;
		}
		return 1;
	}

	for (int i = n - 1; i >= 0; i--) {
		for (int j = i + 1; j < n; j++) {
			// (之前的)向后步骤是矩阵内部元素和右侧都消元，最后的向前步骤只需处理右侧
			a[i][n] -= a[i][j] * a[j][n];
		}
	}
	return 0;
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= n; j++) {
			cin >> a[i][j];
		}
	}

	int t = gauss();

	if (t == 2) cout << "No solution" << endl;
	else if (t == 1) cout << "Infinite group solutions" << endl;
	else {
		for (int i = 0; i < n; i++) printf("%.2f\n", a[i][n]);
	}

	return 0;
}

异或线性方程组

思路：基本一样，但判据改为是否为0 / 1 ，以及利用异或消元

求组合数

动态规划

思路：类似斐波那契

预处理

使用阶乘数组和其逆元数组，dp计算*

Lucas定理

C(a,b) = C(a % p, b % p) * C(a / p, b / p);

#include <iostream>

using namespace std;

typedef long long LL;

LL qmi(int a, int k, int p) {
	LL res = 1;
	while (k) {
		if (k & 1)	res = (LL)res * a % p;
		a = (LL)a * a % p;
		k >>= 1;
	}
	return res;
}

LL C(LL a, LL b, LL p) {
	LL res = 1;
	for (int i = 1, j = a; i <= b; i++, j--) {
		res = (LL)res * j % p;
		res = (LL)res * qmi(i, p - 2, p) % p;
	}
	return res;
}

LL lucas(LL a, LL b, LL p) {
	if (a < p && b < p) return C(a, b, p);
	return (LL)lucas(a / p, b / p, p) * C(a % p, b % p, p) % p;
}

int main() {
	int n;
	cin >> n;

	while (n--) {
		LL a, b, p;
		cin >> a >> b >> p;
		cout << lucas(a, b, p) << endl;
	}

	return 0;
}

Nim游戏

Nim游戏模版

思路：对所有数求异或，若结果不为0必胜，否则必输

台阶Nim游戏

思路：由于只有从第一级台阶才能到达地面“消除”石子，故对所有奇数编号的石子求异或

集合Nim游戏

思路：通过SG函数将状态转换为标准Nim游戏中的一堆石子，从而将所有SG值取异或得到答案

#include <iostream>
#include <algorithm>
#include <cstring>
#include <unordered_set>

using namespace std;

const int N = 110, M = 10010;

int n, k;
int f[M], s[N];

int sg(int x) {
	// 记忆化搜索
	if (f[x] != -1) return f[x];

	// 用集合存储所有可取到的值
	unordered_set<int> S;
	for (int i = 0; i < k; i++) {
		int sum = s[i];
		if (x >= sum) {
			S.insert(sg(x - sum));
		}
	}

	// SG函数的值是取不到的最小自然数(可以想象为链条从这里断开)
	for (int i = 0;; i++) {
		if (!S.count(i))
			return f[x] = i;
	}
}

int main() {
	cin >> k;
	memset(f, -1, sizeof f);
	for (int i = 0; i < k; i++) cin >> s[i];

	cin >> n;
	int res = 0;
	while (n--) {
		int x;
		cin >> x;
		res ^= sg(x);
	}

	if (res) cout << "Yes" << endl;
	else cout << "No" << endl;

	return 0;
}

拆分Nim游戏

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_set>

using namespace std;

const int N = 110;

int n;
int f[N];

int sg(int x) {
	if (f[x] != -1) return f[x];

	unordered_set<int> S;
	// 取出原先石子，放入的新石子，每堆规模不超过原先，不妨设i那堆石子更多
	for (int i = 0; i < x; i++) {
		for (int j = 0; j <= i; j++) {
			// 将新的两堆合并(取异或)
			S.insert(sg(i) ^ sg(j));
		}
	}

	for (int i = 0;; i++)
		if (!S.count(i)) return f[x] = i;
}

int main() {
	cin >> n;
	memset(f, -1, sizeof f);

	int res = 0;
	while (n--) {
		int x;
		cin >> x;
		res ^= sg(x);
	}

	if (res) cout << "Yes" << endl;
	else cout << "No" << endl;

	return 0;
}