【数论】Part 1

### Part 1 Part 1 比较基础，为数论基础，练习题都较为简单，但也会有一些比较困难的思维题。 #### 最大公倍数 - $\gcd$ 辗转相除即可，可以压行做到一行 $\gcd$。 ```cpp long long gcd (long long a, long long b) {return b == 0 ? a : gcd(b, a % b);} ``` 利用 $a \times b=\gcd(a,b) \times \text{lcm}(a,b)$ 可以求出 $\text{lcm}(a,b)$。 练习题： - [GDCOFTI - Greatest Common Divisor Of Three Integers](https://www.luogu.com.cn/problem/SP27561) / [GCD](https://www.luogu.com.cn/problem/UVA11417) 板子 - [高橋君と青木君の好きな数](https://www.luogu.com.cn/problem/AT1741) 差不多是板子，得到 $\gcd(a,b)$ 后求 $n$ 是 $\gcd(a,b)$ 的多少倍即可 - [GCD LCM](https://www.luogu.com.cn/problem/UVA11388) 知道 $\gcd$ 是 $\rm lcm$ 的约数这道题就很好做了 - [[Code+#1] 晨跑](https://www.luogu.com.cn/problem/P4057) 板子题，分析出答案为 $\text{lcm}(a,b,c)$ 就很好做了 - [I'm bored with life](https://www.luogu.com.cn/problem/CF822A) 板子题，知道 $n!$ 是 $(n+1)!$ 的约数这题就很板子了 - [【XR-2】缘分](https://www.luogu.com.cn/problem/P5436) 需要一小点数学分析，知道 $n$ 和 $n-1$ 互质即可，答案即为 $n \times (n-1)$ - [比例简化](https://www.luogu.com.cn/problem/P2118) 差不多是板子，只需要得出分子分母在 $[1,L]$ 即可 - [Modified GCD](https://www.luogu.com.cn/problem/CF75C) 只要知道 $a$ 和 $b$ 的所有公约数是 $\gcd(a,b)$ 的约数，然后进行二分查找即可 - [Border](https://www.luogu.com.cn/problem/CF1010C) 比较清新的构造题，得到 $\forall i\in [0,k),i\equiv 0\pmod{\gcd(a_1,a_2,\cdots,a_n,k)}$，$i$ 都可以由 $a_1,a_2,\cdots,a_n$ 中的若干个数相加即可 - [[BalticOI 2020/2014 Day0] Roses](https://www.luogu.com.cn/problem/P6767) 数学分析题，但是在分析怎样得到 $\gcd$ 这方面比较困难，是道比较有意思的题 - [[POI 2019] Najmniejsza wspólna wielokrotność](https://www.luogu.com.cn/problem/P6659) 需要对 $\rm lcm$ 的性质进行分析，分析出枚举的范围即可 #### 质数 - prime 无非就是几种判断质数的方法： - $n$ 不大的时候暴力 - $n$ 大的话就欧拉筛 欧拉筛就是扫一遍然后标记对于每个质数的倍数。 练习题： - [【模板】线性筛素数](https://www.luogu.com.cn/problem/P3383) / [素数个数](https://www.luogu.com.cn/problem/P3912) 板子 - [质因数分解](https://www.luogu.com.cn/problem/P1075) 差不多是板子，因为是两个质数的乘积，所以只需要从 $2$ 开始枚举最小能被 $n$ 整除的质数即可 - [A % B Problem](https://www.luogu.com.cn/problem/P1865) 板子，吐槽这个 Crossing the Line 的特判没啥意义 - [素数密度](https://www.luogu.com.cn/problem/P1835) 跟 A % B Problem 差不多，但，$L,R$ 比较大，但是 $R-L$ 比较小，所以区间筛法即可（听说筛 $[2,\sqrt{2147483647}]$ 也可？） - [三素数数](https://www.luogu.com.cn/problem/P2359) 小清新 dp 题，但是最后要用到素数筛（为什么列举这道题是因为想哪里判断质数比较困难） 一些题目本身跟素数无关最后来一个判断素数收尾的题目没放，感觉跟素数没啥关系。