唐巧的博客

唐巧的博客

马上订阅 唐巧的博客 RSS 更新: https://blog.devtang.com/atom.xml

CSPJ 教学思考：数学题

2025年4月12日 21:40

数学题是信息学竞赛中重要的一类题目，通常包括几何、数论、容斥原理等。

本文将相关的题目归纳整理，用于教学。

质数相关

判断一个数是否为质数

此算法是很多数学相关题目的基础，在 GESP 二级中也有涉及。例如：B3840 找素数。

其核心代码是：

1
2
3
4
5
6
bool isPrime(int a) {
    for (int i = 2; i*i <=a; i++) {
        if (a%i == 0) return false;
    }
    return true;
}

初学者在写的时候，要注意 i*i 与 a 的比较是小于等于。

质因数分解

质因数分解的方法是从 2 开始试商，如果发现能整除，就把被除数中该因数去掉，关键代码是：

1
while (N % i == 0) N /= i;

这样经过几轮下来，N 的值会变得很小，最后 N 如果不为 1，N 就是最后一个质因数。

完整代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
vector<int> prime_facs(int N) {
  vector<int> result;
  for (int i = 2; i * i <= N; i++) {
    if (N % i == 0) {  
      while (N % i == 0) N /= i;
      result.push_back(i);
    }
  }
  if (N != 1) {  // 说明再经过操作之后 N 留下了一个素数
    result.push_back(N);
  }
  return result;
}

练习题：

B3969 GESP202403 五级 B-smooth 数 的参考代码：

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
#include <bits/stdc++.h>
using namespace...
剩余内容已隐藏
查看完整文章以阅读更多
查看完整文章