YuriCode
0%

数学知识

发表于 更新于 分类于
本文字数： 6.1k 阅读时长 ≈ 6 分钟

质数

试除法判定质数

质数（Prime Number）是指大于1的自然数中，除了1和它本身以外，不能被其他正整数整除的数。换句话说，质数只有两个正因数：1和它本身。例如，2、3、5、7、11等都是质数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//有 d | n
//显然（n / d) | d 也成立
//所以所有枚举的数只需要满足d <= n / d 就可以了
//不推荐使用d <= sqrt(n)，因为每次执行的时候都会调用一次sqrt函数
//也不推荐使用d * d <= n，因为当n接近于INT_MAX时存在溢出风险

bool is_prime(int n)
{
	if (n < 2) return 0;
	for (int i = 2; i <= n / i; i++) {
		if (n % i == 0) return 0; 
	}
	return 1;
}

分解质因数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

//n中最多只包含一个大于sqrt(n)的质因子
//使用反证法，如果包含两个a, b那么存在a * b > n这与已知矛盾

void divide(int N)
{
	int n = N;
	for (int i = 2; i <= N / i; i++) {
		if (n % i == 0) {
			int sum = 0;
			while (n % i == 0) {
				n /= i;
				sum++;
			}
			cout << i << " " << sum << endl;
		}
	}
	if (n > 1) cout << n << " " << 1 << endl;
}

<= k的最大的 n 的除数

https://codeforces.com/problemset/problem/1360/D

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
#define int long long
using namespace std;


void solve()
{
	int n, k;
	// 我们要找到 <= k的最大的 n 的除数
	cin >> n >> k;
	int ans = n;
	for (int i = 1; i <= n / i; i++) {
		if (n % i== 0) {
			// a * b <= n
			if (i <= k) {
				ans = min(ans, n / i);
			}
			if (n / i <= k) {
				ans = min(ans, i);
			}
		}
	}
	cout << ans << endl;
} 

signed main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t = 1;
	cin >> t;
	while(t--){
		solve();
	}
	
	return 0;
}

埃氏筛法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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]) continue;
		//记录素数
		primes[cnt++] = i;
		//筛选倍数
		for (int j = i + i;  j <= n; j += i) {
			st[j] = 1;
		}
	}
}

线性筛法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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;
		//这里的写法可以看作primes[j] * i <= n
		//也就是在i确定的时候可以选取哪几个素数
		for (int j = 0; primes[j] * i <= n; j++) {
			st[primes[j] * i] = 1;
			//遍历到最小质因数的时候退出循环
			if (i % primes[j] == 0) break;
 		}
	}
}

约数

试除法求约数

1
2
3
4
5
6
7
8
9
10
11
12
vector<int> get_divisors(int n)
{
	vector<int> ans;
	for (int i = 1; i <= n / i; i++) {
		if (n % i == 0) {
			ans.push_back(i);
			if (i != n / i) ans.push_back(n / i);	
		}
	}
	sort(ans.begin(), ans.end());
	return ans;	
}

约数个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
//由算术基本定理
//N = P1 ^ a1 + P2 ^ a2 + ··· + Pk ^ ak;
//对于每一个数，都有(ai + 1)次选法，因为最多可以选ai个这个数，最少什么都不选
//所以约数的个数就是(a1 + 1)(a2 + 1)···(ak + 1) 

//用分解质因数的方法很容易实现
const int mod = 1e9 + 7;

unordered_map<int, int> cnt;

void divide(int N)
{
	int n = N;
	for (int i = 2; i <= N / i; i++) {
		if (n % i == 0) {
			while (n % i == 0) {
				n /= i;
				cnt[i]++;
			}
		}
	}
	if (n > 1) cnt[n]++;
}

void solve()
{
	int n;
	cin >> n;
	vector<int> arr(n);
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
		divide(arr[i]);
	}
	int sum = 1;
	for (auto x : cnt) {
		sum *= (x.second + 1);
		sum %= mod;
	}
	cout << sum << endl;
}

约数之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
//(P1 ^ 0 + P1 ^ 1 + ··· + P1 ^ a1) ··· （Pk ^ 0 + Pk ^ 1 + ··· + Pk ^ ak)
//用乘法分配律展开式子后结果是显然的
const int mod = 1e9 + 7;

unordered_map<int, int> cnt;

void divide(int N)
{
	int n = N;
	for (int i = 2; i <= N / i; i++) {
		if (n % i == 0) {
			while (n % i == 0) {
				n /= i;
				cnt[i]++;
			}
		}
	}
	if (n > 1) cnt[n]++;
}

void solve()
{
	int n;
	cin >> n;
	vector<int> arr(n);
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
		divide(arr[i]);
	}
	int ans = 1;
	for (auto x : cnt) {
		int temp = 1;
		while (x.second--) {
			temp = (temp * x.first + 1) % mod;
		}
		ans = ans * temp % mod;
	}
	cout << ans << endl;
}

最大公约数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//性质1
//d | a , d | b --> d | x * a + y * b
//证明：
//d | a --> d * k1 = a;
//d | b --> d * k2 = b;
//x * a + y * b = x * d * k1 + y * d * k2
//d | x * a + y * b

//辗转相除法原理
//(a, b) = (b, a % b);

//a % b = a - a / b * b;
//c = a / b
//等价与证明(a, b) = (a, a - c * b)
//由性质1，这是显然的
 

int gcd(int a, int b)
{
	//b不是0返回gcd(b, a % b)
	//b是0返回a
	return b ? gcd(b, a % b) : a;
}

卡特兰数

https://www.luogu.com.cn/problem/P1044

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <bits/stdc++.h>
#define int long long
using namespace std;

int f[20];

void solve() {
	// 我们可以把入栈和出栈抽象为坐标系上面的折线
	// 入栈就是由(x, y) -> (x + 1, y + 1)
	// 出栈就是(x, y) -> (x + 1, y - 1)
	// 从(0, 0) -> (2 * n, 0)
	// 入栈和出栈的次数显然都是n
	// 即C(n, 2 * n);
	// 但是这样可能出现栈已经空了，但是还在弹出元素这样的非法情况
	// 如果出现这种情况，不妨把第一次出现跨越y轴到y = -1之后的所有的都按y = -1对称
	// 于是终点变为了(2 * n, -2)
	// 所以在这种情况下入栈n - 1，出栈n + 1
	// 总共有C(n - 1, 2 * n)种情况
	// 所以一共有C(n, 2 * n) - C(n - 1, 2 * n)
	
	//	由于x是最后一个出栈的，所以可以将已经出栈的数分成两部分
	//	比x小的数有x-1个，所以这些数的全部出栈可能为f[x-1]
	//	比x大的数有n-x个，所以这些数的全部出栈可能为f[n-x]
	//	这两部分互相影响，所以一个x的取值能够得到的所有可能性为f[x-1] * f[n-x]
	// f[n] = f[0] * f[n - 1] + f[1] * f[n - 2] + ... + f[n - 1] * f[0]
 	int n; 
	cin >> n;
	f[0] = 1;
	f[1] = 1;
	for (int i = 2; i <= n; i++) {
		for (int j = 0; j < i; j++) {
			f[i] += f[j] * f[i - j - 1];
		}
	}
	cout << f[n] << endl;
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t = 1;
//	cin >> t;
	while (t--) {
		solve();
	}
	
	return 0;
}

欧拉函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// 欧拉函数
// Φ(N)：1 ~ N 中与 N 互质的数的个数
// N = p1 ^ α1 * p2 ^ α2 * ... * pk * αk
// Φ(N) = N * (1 - 1 / p1) * (1 - 1 / p2) * ... * (1 - 1 / pk)

// 证明
// 1，从1 ~ N中去掉所有p1, p2, ... pk的倍数
// N - N / p1 - N / p2 - ... - N / pk
// 有可能有些数会重复去除
// 2，加上所有pi * pj 的倍数
// 3，减去所有pi * pj * pk的倍数
// .
// .
// .
// 把这个式子合并就能得到结论
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;
}

筛法求欧拉函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
const int N = 1e6 + 10;
int primes[N], cnt;
int phi[N];
bool st[N];

int get_eulers(int n)
{
	phi[1] = 1;
	for (int i = 2; i <= n; i++) {
		if (!st[i]) {
			primes[cnt++] = i;	
			// 质数 p 的欧拉函数为p - 1
			phi[i] = i - 1;
		}
		for (int j = 0; primes[j] * i <= n; j++) {
			st[primes[j] * i] = 1;
			if (i % primes[j] == 0) {
				// 欧拉函数的大小与质因子的数量无关，只与数字大小和种类有关
				phi[primes[j] * i] = primes[j] * phi[i]; 
				break;	
			}
			// 当 i % primes[j] != 0 时
			// phi[primes[j] * i] = primes[j] * phi[i] * (1 - 1 / primes[j])
			phi[primes[j] * i] = phi[i] * (primes[j] - 1);
		}
	}
	int sum = 0;
	for (int i = 1; i <= n; i++) {
		sum += phi[i];
	}
	return sum;
}

欧拉定理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 欧拉定理
// 如果gcd(a, n) = 1
// 那么 a ^ phi[n] ≡ 1 (mod n)

// 证明
// 在 1 ~ n 中与 n 互质的数不妨设为
// a1, a2, a3, ... , aphi[n]
// 不妨构造一个数列
// a * a1, a * a2, a * a3, ... , a * aphi[n]
// 因为 a 与 n 互质，a1, a2, a3, ... , aphi[n] 也与 n 互质，所以乘积也和 n 互质
// 假设存在a * ai ≡ a * aj (mod n) (i != j)
// a 和 n 互质，所以可以同时消掉 a
// 得到 ai ≡ aj，这是不可能的，与假设矛盾
// 所以这个式子两两不同
// 把这个数列每个式子 mod n 就可以与原数列一一映射
// a1 * a2 ... aphi[n] ≡ a ^ phi[n] * a1 * a2 ... aphi[n] (mod n)
// a ^ phi[n] ≡ 1 (mod n)

费马小定理

1
2
3
4
5
6
// 费马小定理
// 如果gcd(a, n) = 1
// 那么 a ^ (p - 1) ≡ 1 (mod n)

// 证明
// 由欧拉定理立即可以得到