Czj's Blog

第六讲-图论基础、数学与计算几何

发表于 更新于 分类于 ，
本文字数： 15k 阅读时长 ≈ 14 分钟

作业链接

[蓝桥杯] 第六讲：图论基础、数学与计算几何 - 题单 - 洛谷 | 计算机科学教育新生态

AC 代码

P3366 【模板】最小生成树 - 洛谷

最小生成树是在一个联通图中，寻找特定的点或边，构成一个边权最小的树。选择边的做法称为克鲁斯卡尔算法（Kruskal），同时为了记录哪些点已经被选择，避免选择的边导致最终形成图而不是树，还需要使用并查集记录点的信息。

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
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 9, M = 2e5 + 9;
int cnt, n, m,  p[N], ans, a, b, w;
typedef struct node {
	int a, b, w;
} edge;
edge e[M];
bool cmp(edge x, edge y) {
	return x.w < y.w;
}
int find(int x) {
	if (p[x] != x) {
		p[x] = find(p[x]);
	}
	return p[x];
}
int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> a >> b >> w;
		e[i].a = a, e[i].b = b, e[i].w = w;
	}
	for (int i = 1; i <= n; i++) p[i] = i;
	sort(e, e + m, cmp);
	for (int i = 0; i < m; i++) {
		a = e[i].a, b = e[i].b, w = e[i].w;
		if (find(a) != find(b)) {
			p[find(a)] = find(b);
			ans += w;
			cnt++;
		}
	}
	if (cnt == n - 1) cout << ans;
	else cout << "orz";
	return 0;
}

P9235 [蓝桥杯 2023 省 A] 网络稳定性 - 洛谷

题目大意： 定义一条路径的权值为路径上所有边权的最小值，两点之间的权值为所有路径权值的最大值

知识点： 克鲁斯卡尔重构树 + 最近公共祖先

通过克鲁斯卡尔最大重构树按边权从大到小将边转化为新的点，将边权转化为点权。 在重构树上，两个点的最近公共祖先的点权即为题意中要求的两点间权值。 因为克鲁斯卡尔最大重构树满足树上的点权是尽可能大的唯一路径， 且由于重构树是自下而上构建的，因此祖先节点的权值一定是路径上的最小值 因此对于图上两点 x,y 的询问，可以直接转化为求重构树上的 lca(x,y) 的点权

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include<bits/stdc++.h>
using namespace std;
/*
克鲁斯卡尔重构树与克鲁斯卡尔生成树的逻辑基本一致
首先需要对边排序，本题从大到小，然后用并查集维护是否连通
若不连通则创建新的节点，点权为边权，连接原本边所连接的点的祖先（类似哈夫曼树）
重构树的根节点点权最小，越往叶子节点权值越大，叶节点为原先存在的点，权值为零
由于本题中给出的是一个图，因此转化为重构树后不一定联通，实际得到的是森林
*/
const int N = 2e5+9, M = 3e5+9; // 点需要开两倍，因为重构树会增加至多 n-1 个新的节点，其中 n 为点的数量
int p[N]; // 并查集
int val[N]; // 点的权值
vector<int> g[N]; // 用于存储重构树的边
int n, m, q, x, y;
// 结构体存边用于排序
struct node {
	int x, y, w; // 两端的点和边权
} e[M];
bool cmp(node x, node y) {
	// 定义边的比较方式为大边权优先
	return x.w > y.w;
}
int find(int x) {
	// 路径压缩
	if (x != p[x]) p[x] = find(p[x]); // 继续递归且将当前 x 的祖先也指向最终祖先
	return p[x];
}
void kruskal() {
	// 排序边权
	sort(e, e + m, cmp);
	int idx = n + 1;// 新节点的编号从已有节点之后开始
	// 初始化并查集
	for (int i = 1; i <= 2 * n; i++) { // 点可能会在建树的时候增加到 2 * n
		p[i] = i;
	}
	// 遍历所有边建树
	for (int i = 0; i < m; i++) {
		int a = e[i].x, b = e[i].y, c = e[i].w;
		// 找到点的祖先
		int pa = find(a), pb = find(b);
		if (pa == pb) continue; // 两个点有相同的祖先，说明已经被链接过，且当前边的边权更小，直接放弃
		// 创建新的节点连接这两个连通块
		p[pa] = idx, p[pb] = idx; // 修改指向表示 pa 和 pb 的共同祖先是 idx
		// 邻接表记录这两条边的关系，根节点指向子节点的单向边也不影响求 lca
		g[idx].push_back(pa);
		g[idx].push_back(pb);
		val[idx] = c; // 更新点权
		idx++;
	}
}
// 用于记录 lca
int dep[N]; // 点的深度
int fa[N][26]; // 跳表 fa[i][j] 表示点 i 向上跳 2^j 次对应的祖宗节点
void dfs(int u, int father) {
	// 预处理所有点的深度和父节点
	dep[u] = dep[father] + 1;
	fa[u][0] = father; // 2^0 = 1 即向上跳一步

	// 向上跳
	for (int i = 1; i < 25; i++) {
		// 这里虽然 i 到 29 时表示向上跳了 2^29 步，但是这个节点如果不存在就自然为 0 了，不影响结果，因此不用考虑跳的过程中越界
		fa[u][i] = fa[fa[u][i - 1]][i - 1]; // 向上跳 2^i 步相当于先跳到 2^(i-1) 的位置来到 fa[u][i-1]，再跳 2^(i-1)
	}
	// 向下搜索
	for (auto t : g[u]) {
		if (t != father)dfs(t, u); // 避免回到父节点。事实上这里只存了父节点到子节点的单向边，if 是一直成立的
	}
}
int lca(int x, int y) {
	// 保证 x 是更深的，让其先往上跳
	if (dep[x] < dep[y]) {
		swap(x, y);
	}
	// 先大跳后小跳
	for (int i = 25; i >= 0; i--) {
		// 如果跳上去之后，x 的深度不超过 y 则执行这个跳跃，最终 x 和 y 的深度会一致
		if (dep[fa[x][i]] >= dep[y]) {
			x = fa[x][i];
		}
	}
	// 要判断 y 是不是 x 的直接祖先
	if (x == y)return x;
	// 此时深度一致，可以一起跳，直到父节点一致
	for (int i = 25; i >= 0; i--) {
		if (fa[x][i] != fa[y][i]) // 要注意这里使用祖先节点来判断是否相同
			x = fa[x][i], y = fa[y][i];
	}
	// 最后向上跳一步得到共同祖先
	return fa[x][0];
}
int main() {
	cin >> n >> m >> q;
	// 读入边
	for (int i = 0; i < m; i++) {
		cin >> e[i].x >> e[i].y >> e[i].w;
	}
	// 建立重构树
	kruskal();
	// 对森林里的每一棵求其上所有点的 lca
	for (int i = 1; i <= 2 * n; i++) {
		if (i == p[i]) { // 说明这是根节点
			dfs(i, 0); // 深搜得到这棵树的节点深度和跳表
		}
	}
	// 处理询问
	while (q--) {
		cin >> x >> y;
		if(find(x)!=find(y))
		{
			// 不连通，直接返回不可达
			cout<<-1<<endl;
		}
		else cout << val[lca(x, y)] << "\n";
	}
	return 0;
}

P4779 【模板】单源最短路径（标准版） - 洛谷

最短路算法总结

记图的边有 m 条，点有 n 个

  • 单源最短路

    • 边权均为正（贪心）

      • 朴素 dijkstra \(O(n^2)\) 适用于稠密图，即 m>>n，存邻接表。
      • 堆优化 dijkstra 选点 \(O(mlogn)\)

    • 存在边权为负

      • Bellman-Ford 处理有边数限制的最短路。双重循环：外层遍历点，内层遍历边。\(O(nm)\)
      • SPFA 一般 \(O(m)\) ,最坏 \(O(nm)\)。宽搜优化，网格状图可能使复杂度升高

  • 多源最短路

    Floyd 算法 \(O(n^3)\) 可以处理负权边，不能处理负权回路。本质是优化过的三维动态规划

区别

Bellman-ford 可以处理任意带负权边和负权环的图，SPFA 可以处理带负权边的图，Dijkstra 只能处理带正权边的图；当然，从时间复杂度的效率来讲，是反过来的

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
//堆优化dijkstra，链式前向星存图
#include <bits/stdc++.h>
using namespace std;
int n, m, s;
typedef pair<int, int> PII;
const int N = 1e5 + 9, M = 2 * N;
int h[N], e[M], ne[M], w[M], idx;
void add(int a, int b, int c) {
	e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
int dist[N];//s到所有点的最小距离
bool st[N];//防止重复入队
void dijkstra() {
	for (int i = 1; i <= n; i++) dist[i] = INT_MAX;
	dist[s] = 0;
	priority_queue<PII, vector<PII>, greater<PII> > heap; //小根堆
	heap.push({0, s}); //入队
	while (heap.size()) {
		auto t = heap.top();
		heap.pop();
		int index = t.second, distance = t.first;
		if (st[index]) continue; //如果这个点已经检查过了，那就跳过
		st[index] = 1;//标记
		for (int i = h[index]; i != -1; i = ne[i]) { //检查出边
			int j = e[i];
			if (dist[j] > distance + w[i]) {
				dist[j] = distance + w[i];
				if (!st[j]) {
					heap.push({dist[j], j});
				}
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		printf("%d ", (dist[i] == INT_MAX ? INT_MAX : dist[i]));
	}
}
int main() {
	scanf("%d %d %d", &n, &m, &s);
	memset(h, -1, sizeof h);
	for (int i = 0; i < m; i++) {
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		add(a, b, c);
	}
	dijkstra();
	return 0;
}

P8802 [蓝桥杯 2022 国 B] 出差 - 洛谷

将题目中定义的双向路径改为两条单向路径，城市隔离时间加到单向边的边权上，则问题直接转化为求从 1 到 N 的最短路，同理使用堆优化 dijkstra 即可。

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
51
52
53
54
55
56
57
58
#include<bits/stdc++.h>
using namespace std;
int n, m;
typedef pair<int, int> PII;
const int N = 1e3+9;
// 邻接表存图
vector<PII> g[N];
int w[N], a, b, c,dist[N];
bool vis[N];

void dijkstra(int st,int ed)
{
	memset(dist,0x3f,sizeof dist);
	priority_queue<PII,vector<PII>,greater<PII>> q;// 小根堆，先存距离再存编号
	q.push({0,1});// 出发点的代价为0
	dist[st] = 0;

	while(q.size())
	{
		auto t = q.top();
		q.pop();

		int idx = t.second,dis = t.first;

		if(vis[idx])continue;

		vis[idx] = 1;
		// 用这个点来松弛与其相连的那些点
		for(auto t : g[idx])
		{
			int tmpidx = t.first, tmpdis = t.second;
			if(dist[tmpidx]> tmpdis+dis)
			{
				dist[tmpidx] = tmpdis+dis;
				if(!vis[tmpidx])q.push({dist[tmpidx],tmpidx});
			}
		}
	}
//	for(int i = 1;i<=n;i++)
//	{
//		cout<<dist[i]-w[i]<<endl;
//	}
	cout<<dist[ed]-w[ed];
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> w[i];
	}
	for (int i = 0; i < m; i++) {
		cin >> a >> b >> c;
		g[a].push_back({b,c+w[b]});// 从 a 去到 b 的花费还要计算在 b 被隔离的时间
		g[b].push_back({a,c+w[a]});
	}
	dijkstra(1,n);
	return 0;
}

B3644 【模板】拓扑排序 / 家谱树 - 洛谷

后代关系可以抽象为单向边，即从前辈指向后代。点的入度定义为指向其的边的数量。故输出要求的“每个人的后辈都比那个人后列出”可以转化为按辈分由高到低输出，借助入度和单向边，可以发现入度越小的点，辈分越高。

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
#include <bits/stdc++.h>
using namespace std;
int n, x;
const int N = 1e4 + 9;
int h[N], e[N], ne[N], d[N], idx;
vector<int> ans;
queue<int> q;
void add(int a, int b) {
	e[idx] = b, ne[idx] = h[a], d[b]++, h[a] = idx++;
}

void tp() {
	for (int i = 1; i <= n; i++) {
		if (!d[i]) {
			ans.push_back(i);
			q.push(i);
		}
	}
	while (q.size()) {
		auto t = q.front();
		q.pop();
		for (int i = h[t]; i != -1; i = ne[i]) {
			int j = e[i];
			d[j]--;
			if (!d[j]) {
				ans.push_back(j);
				q.push(j);
			}
		}
	}
	return ;
}

int main() {
	memset(h, -1, sizeof h);
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		while (1) {
			scanf("%d", &x);
			if (!x) break;
			add(i, x);
		}
	}
	tp();
	for (auto x : ans) {
		printf("%d ", x);
	}
	return 0;
}

P8655 [蓝桥杯 2017 国 B] 发现环 - 洛谷

题目大意

原本是树，链接多一条边后变成图，要找到这个图中的环。

问题转化

将树的无向边改为两条单向边后，可以发现叶子节点的入度一定是 1。并且加上边之后，环上的点入度一定为 2，故入度是 1 的点，一定不在环上。因此可以根据入度的值决定是否要删除这个点，最后剩下的一定是在环上的点

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
#include<bits/stdc++.h>
using namespace std;
int n, a, b;
const int N = 1e5+9;
vector<int> g[N], ans;
int in[N];
bool flg;
// 传入只有单边的点，删除这个点
void del(int u) {
//	cout << "delete" << u << endl;
	in[u]--;
	int to = g[u][0];
	in[to]--;
//	cout << to << " " << in[to] << " " << out[to] << endl;
	// 删除完之后，新的单边点出现，连锁
	if (in[to] == 1)del(to);
	return;
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
		in[a]++, in[b]++;
	}
	for (int i = 1; i <= n; i++) {
		// 只有一个边链接到树上的点，剪枝
		if (in[i] == 1) {
			del(i);
		}
	}
	for (int i = 1; i <= n; i++) {
		// 所有单点剪枝后只剩下环
		if (in[i])cout << i << ' ';
	}

	return 0;
}

P1226 【模板】快速幂 - 洛谷

快速幂是通过二进制分解，在 \(logn\) 的复杂度内求出 \(a^n\) 的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a, b, p;

ll qpow(int a, int b, int p) {
	ll ans = 1, tmp = a;
	while (b) {
		if (b & 1) ans = (ans % p * tmp % p) % p;
		tmp = (tmp % p * tmp % p) % p;
		b >>= 1;
	}
	return ans % p;
}

int main() {
	scanf("%lld %lld %lld", &a, &b, &p);
	printf("%lld^%lld mod %lld=%lld", a, b, p, qpow(a, b, p));
	return 0;
}

P3390 【模板】矩阵快速幂 - 洛谷

矩阵乘法也具有结合律，可以和普通乘法一样用快速幂思想加速

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
51
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e2+9, MOD = 1e9+7;
int n;
ll k;
vector<vector<ll>> a(N, vector<ll>(N, 0));
vector<vector<ll>> ans(N, vector<ll>(N, 0));

vector<vector<ll>> mul(vector<vector<ll>> a, vector<vector<ll>> b) {
	vector<vector<ll>> c(n, vector<ll>(n, 0));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < n; k++) {
				c[i][j] = (c[i][j] + (a[i][k] * b[k][j]) % MOD) % MOD;
			}
		}
	}
	return c;
}
vector<vector<ll>> qpow(vector<vector<ll>> a, ll k) {
	vector<vector<ll>> tmp(n, vector<ll>(n, 0));

	for (int i = 0; i < n; i++) {
		tmp[i][i] = 1;
	}

	while (k) {
		if (k & 1LL)tmp = mul(tmp, a);
		a = mul(a, a);
		k >>= 1LL;
	}

	return tmp;
}
int main() {
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> a[i][j];
		}
	}
	ans = qpow(a, k);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cout << ans[i][j] << " ";
		}
		puts("");
	}
	return 0;
}

P1962 斐波那契数列 - 洛谷

矩阵快速幂的应用，斐波那契数列的递推式可以用矩阵乘法表示。

\[ \begin{pmatrix} F_n \\ F_{n-1} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} * \begin{pmatrix} F_2 \\ F_1 \end{pmatrix} \]

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n;
const int MOD = 1e9 + 7;

void mul(ll a[][2], ll b[][2]) {
	ll c[2][2] = {0};
	for (int i =  0; i < 2; i++) {
		for (int j = 0; j < 2; j++) {
			for (int k = 0; k < 2; k++) {
				c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % MOD;
			}
		}
	}
	memcpy(a, c, sizeof c);
}

ll  feb(ll n) {
	ll a[2][2] = {1, 1, 0, 0}, f[2][2] = {1, 1, 1, 0};
	while (n) {
		if (n & 1) mul(a, f);
		mul(f, f);
		n >>= 1;
	}
	return a[0][1];
}

int main() {
	scanf("%lld", &n);
	printf("%lld\n", feb(n - 1));
	return 0;
}

AT_code_festival_qualA_c 2 月 29 日 - 洛谷

题目大意

求一个区间内的闰年数量

解题思路

容斥原理：

闰年是四年一闰，百年不闰，四百年又闰 因此要找 1 到 b 的闰年，只需要求 b 中 4,100,400 的倍数 即 \(\frac{b}{4} - \frac{b}{100} + \frac{b}{400}\) 即为闰年的数量

前缀和：

(1 到 b 的闰年数量) - (1 到 a-1 的闰年数量)就是 a 到 b 的闰年数量

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <bits/stdc++.h>
using namespace std;
int a, b;

int cmp(int y) {
	return y / 4 - y / 100 + y / 400;
}

int main() {
	cin >> a >> b;
	cout << cmp(b) - cmp(a - 1);
	return 0;
}

P10580 [蓝桥杯 2024 国 A] gcd 与 lcm - 洛谷

容斥原理 对于长度为 \(n\) 的序列 \((a_1, a_2, a_3, ... ,a_n)\)，要求满足所有元素的 gcd 是 \(x\)，lcm 是 \(y\)

这说明 \(n\) 个数的最小约数都是 \(x\)，最大倍数都是 \(y\) 同时因为这个序列能满足最小倍数是 \(y\)，最大约数是 \(x\)，说明 \(\frac{y}{x}\) 一定是整数 接下来可以发现对每一个数字 \(a_i\) 都除以 \(x\)，是可以整除的 此时最小公约数为 1，最大公倍数是 \(\frac{y}{x}\)，不妨记 \(t = \frac{y}{x}\)

这样问题转化为从 \((1,2,3, ... ,t)\) 这么多个数字中，任选 \(n\) 个组成要求的序列 但是必须满足选出来的这 \(n\) 个数字中，一定要有一个 1 和一个 \(t\)，这来自最小公约数是 1 和最大公倍数是 \(t\) 的约束

不加任何限制时，首先对 \(t\) 进行质因数分解，得到 \(p_1^{k_1} * p_2^{k_2} * ... * p_c^{k_c}\)，对于每一个 \(p_i\)，\(n\) 个数字有 \([0,k_i]\) 共 \(k_i+1\) 中选择，即贡献 \((k_i+1)^n\)。考虑限制，则 \(n\) 个数字中必须有一个是由 \(k_i = 0,i\in[1,c]\) 组成最终得到 1，还需要有一个是由 \(k_i = k_i,i\in[1,c]\) 组成最终得到 \(t\)。这两种情况都固定了 \(k_i\) 是特定值，因此需要减去 \((k_i)^n\) 种情况。最后还要加上被重复减去的 \([1,k_i-1]\) 共 \((k_i-1)^n\) 种情况。故对每一个质因子的次数 \(k_i\)，其对答案的贡献为 \(f(k_i) = (k_i+1)^n - 2*(k_i)^n + (k_i-1)^n\)。最终答案根据乘法原理有：\(ans = \prod_{i=1}^{c} f(k_i)\)

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<bits/stdc++.h>
using namespace std;
const int mod = 998244353;
typedef long long ll;
int n, q;
ll x, y, t;
vector<ll> k;
void div(ll n) {
	k.clear();

//	cout << "质因数分解：" << n << endl;
	for (int i = 2; i <= n; i++) {
		if (n % i == 0) {
//			cout << i << endl;
			// 是一个质因子
			int tmp = 0; // 记录次方
			while (n % i == 0) {
				n /= i;
				tmp++;
			}
			k.push_back(tmp);
		}
	}
	if (n > 1) {
		// 剩下一个质数
		k.push_back(1);
	}
//	for (auto t : k) {
//		cout << t << " ";
//	}
//	puts("");
}
ll qpow(ll x, ll n) {
	ll ans = 1;
	while (n) {
		if (n & 1)ans = (ans * x) % mod;
		x = (x*x) % mod;
		n >>= 1;
	}
	return ans;
}
ll f(ll k) {
	ll res = 0;
	res = (res + qpow(k + 1, n)) % mod;
	res = (res - 2 * qpow(k, n) % mod) % mod;
	res = (res + qpow((k - 1), n)) % mod;
//	cout << "函数值：" << k << " " << res << endl;
	return res;
}
int main() {
	cin >> q;
	while (q--) {
		ll ans = 1;
		cin  >> x >> y >> n;
		t = y / x;
		// 对 t 进行质因数分解
		div(t);
		// 对每一个因数的次方分别进行容斥
		for (auto t : k) {
			ans = (ans * f(t)) % mod;
		}
		cout << (ans + mod) % mod << "\n";
	}
	return 0;
}

P10390 [蓝桥杯 2024 省 A] 因数计数 - 洛谷

平方重复可以整除的情况，然后容斥处理不符合的情况。

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
51
52
53
54
55
56
57
58
59
60
61
62
#include <iostream>
#define int __int128 // 使用 __int128 需要手写输入输出
using namespace std;

const int N = 1e5 + 9;

int n, a[N], x, mp[N], yinzi[N], beishu[N], ans;
// mp yinzi beishu 分别记录 x 的出现次数，因子个数，倍数个数

int read() {
	int res = 0, p = 1;
	char c;
	c = getchar();
	// 非数字
	while (c < '0' || c > '9') {
		if (c == '-')p = -1;
		c = getchar();
	}
	// 数字
	while (c >= '0' && c <= '9') {
		res = res * 10 + (c - '0');
		c = getchar();
	}
	return p * res;
}

void print(int x) {
	if (x >= 10)print(x / 10);
	putchar((x % 10) + '0');// 输出要是字符
}

signed main() {
	n = read();
	for (int i = 1; i <= n; i++)mp[read()]++;
	// 预处理每个数字的因子和倍数
	for (int i = 1; i < N; i++) {
		if (mp[i]) {
			for (int j = i + i; j < N; j += i) {
				if (mp[j]) {
					// i 和 j 都存在
					beishu[i] += mp[j], yinzi[j] += mp[i];
				}
			}
			// 相同的值既是倍数也是因子（不能计自己）
			beishu[i] += mp[i] - 1, yinzi[i] += mp[i] - 1;
		}
	}
	for (int i = 1; i < N; i++) {
		if (mp[i])ans += beishu[i] * mp[i];// 原始数存在才能记
	}
	ans *= (ans + 1);
	for (int i = 1 ; i < N; i++) {
		if (mp[i]) {
			ans -= mp[i] * beishu[i] * beishu[i];
			ans -= mp[i] * yinzi[i] * yinzi[i];
			ans -= 2 * (mp[i] * beishu[i] * yinzi[i]);
			ans += mp[i] * (mp[i] - 1);
		}
	}
	print(ans);
	return 0;
}

P8720 [蓝桥杯 2020 省 B2] 平面切分 - 洛谷

点线面问题

涉及的定理有：

  1. 每增加一条不与之前重合的直线，则划分出 \(1\) 块平面
  2. 直线与之前的直线交点为 \(x\) 个，则划分出 \(x\) 块平面

交点的计算方式：不妨设交点为 \((x,y)\) 则用 \(k_i,b_i\) 表示的直线联立方程为

\[ \begin{align} y &= k_1 x + b_1 \\ y &= k_2 x + b_2 \end{align} \]

两式相减，解得：\(x = \frac{(b_1 - b_2)}{(k_1 -k_2)}\)，将 \(x\) 带回原方程有 \(y = k_1 * x + b1 = k_2*\frac{(b_1 - b_2)}{(k_1 -k_2)} + b1\)

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
#include<bits/stdc++.h>
using namespace std;
typedef pair<double, double> PDD;

set<PDD> lines; // 直线集合
double a, b, ans;
int count(double a, double b) {
	set<PDD> ps; // 交点集合
	double x, y, c, d;
	// 遍历之前的直线
	for (auto t : lines) {
		c = t.first, d = t.second;
		if (c == a) {
			// 斜率相同不会有交点，需要跳过
			continue;
		}
		// 求交点
		x = (d - b) / (c - a);
		y = a * x + b;

		ps.insert({x, y});
	}
	return ps.size();
}
int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a >> b;
		// 使用集合来跳过重合的线
		int cnt = lines.size(); // 先记录没插入前的集合大小
		lines.insert({a, b}); // 插入这个点，set 会自动去重
		if (cnt != lines.size()) { // 如果大小不同，说明插入的是新的
			ans += count(a, b) + 1; // 1 来自于直线本身，还要计算交点
		}
	}
	cout << ans + 1; // 原始平面也算一块
	return 0;
}