Guchen's Blog

发表于2025-06-20

Math判定质数判定质数假设 $d | n$ ，则有 $\frac{n}{d} | n$ ，不妨设 $d \lt \frac{n}{d}$，则 $d < \sqrt{n}$，因此试除法判定质数的判断条件可以写为： 1for(int i = 2; i <= n / i; ++ i) 质数筛任意一个合数 $m$ 都可以写成 $m = p \times q$ ，其中 $p$ 为最小质因子，因此可以用线性筛。 123456789101112bool st[N]; //用以记录哪些数被筛除int primes[N], cnt;void ger_primes() { for(int i = 2; i <= n; ++ i) { if(!st[i]) primes[cnt ++] = i; // 没被筛的一定是质数 for(int j = 0; primes[j] <= n / i; ++ j) { st[primes[j] * i] = true; if(i % ...

greedy

发表于2025-06-20

贪心算法区间问题区间覆盖问题题目描述给定 $N$ 个闭区间 $[a_i, b_i]$，请你在数轴上选择尽量少的点，使得每个区间内至少包含一个选出的点。注意：位于区间端点上的点也算作区间内。输入格式第一行包含一个整数 $N$，表示区间的数量。接下来 $N$ 行，每行包含两个整数 $a_i$ 和 $b_i$，表示一个区间的两个端点。输出格式输出一个整数，表示所需的点的最小数量。数据范围 $1 \leq N \leq 10^5$ $-10^9 \leq a_i \leq b_i \leq 10^9$ 输入样例1234541 32 45 76 8 输出样例12 解题思路区间按右端点非递减排序，每次选取右端点。证明假设最优解是 $res$ ，贪心算法的解是 $cnt$ ，那么有: $res \leq cnt$ ；按照贪心算法，只有区间不相交时才会选取，意即至少有 $cnt$ 个不相交的区间，至少需要 $cnt$ 个点，那么有 $res \ge cnt$ ；因此 $res = cnt$ 。 Code12345678910111213141516171819202122232 ...