目录

一、约数定义算术基本定理的推论求$N$的正约数集合 - 试除法求1~N每个数的正约数集合 - 倍数法AcWing198. 反素数 二、最大公约数最大公约数与最大公倍数更相减损术luogu P1072 （NOIP2009）Hankson的趣味题 三、互质与欧拉函数三种方法求欧拉函数积性函数欧拉函数性质luogu P2158 [SDOI2008]仪仗队 / AcWing 201. 可见的点

声明： 本系列博客是《算法竞赛进阶指南》+《算法竞赛入门经典》+《挑战程序设计竞赛》的学习笔记，主要是因为我三本都买了 按照《算法竞赛进阶指南》的目录顺序学习，包含书中的少部分重要知识点、例题解题报告及我个人的学习心得和对该算法的补充拓展，仅用于学习交流和复习，无任何商业用途。博客中部分内容来源于书本和网络（我尽量减少书中引用），由我个人整理总结（习题和代码可全都是我自己敲哒）部分内容由我个人编写而成，如果想要有更好的学习体验或者希望学习到更全面的知识，请于京东搜索购买正版图书：《算法竞赛进阶指南》——作者李煜东，强烈安利，好书不火系列，谢谢配合。

---

下方链接为学习笔记目录链接（中转站）

学习笔记目录链接

---

ACM-ICPC在线模板

---

一、约数

定义

若整数n除以整数d的余数为0，即d能整除n，则称 $\mathtt{d}$ 是 n的约数，n是d的倍数，记为 $\mathtt{d}|\mathtt{n}$

算术基本定理的推论

由算数基本定理得正整数N可以写作$N=p_1^{C_1}\times p_2^{C_2}\times p_3^{C_3}\cdots \times p_m^{C_m}$

N的正约数个数为($\Pi$是连乘积的符号，类似$\sum$)

$$(c_1+1)\times (c_2+1)\times \cdots (c_m+1)={\Pi }_{i=1}^m(ci+1)$$ N的所有正约数和为

$$(1+p_1+p_1^2+\cdots +p_1^{c_1})\times \cdots \times (1+p_m+p_m^2+\cdots +p_m^{c_m})=\prod _{i=1}^m(\sum _{j=0}^{c_i}(p_i{)}^j)$$

求$N$的正约数集合 - 试除法

约数总是成对出现，所以只需要枚举到$\sqrt{n}$即可。（除了完全平方数，只有一个$\sqrt{n}$）

vector<int>factor; int m; int main() { scanf("%d", &n); for(int i = 1; i * i <= n; ++ i){ if(n % i == 0){ factor.push_back(i); if(i != n / i) factor.push_back(n / i); } } for(int i = 0; i < factor.size(); ++ i){ printf("%d\n", factor[i]); } return 0; }

推论：一个整数N的约数个数上界为$2\sqrt{\mathtt{n}}$

求1~N每个数的正约数集合 - 倍数法

时间复杂度为$O(nlogn)$（每一个约数为$O(1)$总共$nlogn$个）

int main() { scanf("%d", &n); for(int i = 1; i <= n; ++ i){ for(int j = 1 ;j * i <= n; ++ j){ factor[i * j].push_back(j); } } for(int i = 1; i <= n; ++ i){ cout << i << ": "; for(int j = 0; j < factor[i].size(); ++ j) printf("%d ", factor[i][j]); puts(""); } return 0; }

推论：1~N中每个数的约数的总和大概为$NlogN$。

AcWing198. 反素数

二、最大公约数

最大公约数与最大公倍数

最多$O(logn)$

int gcd(int a, int b){ return b == 0 ? a : gcd(b, a % b); } int lcm(int a,int b){ return a / gcd(a,b) * b;//先除后乘，以免溢出 }

$\forall a,b\in N,gcd(a,b)\ast lcm(a,b)=a\ast b;$

更相减损术

$$\begin{gathered} \forall a,b\in N,a>b,有gcd(a,b)=gcd(b,a-b)=gcd(a,a-b) \\ \forall a,b\in N,有gcd(2a,2b)=2gcd(a,b) \end{gathered}$$

luogu P1072 （NOIP2009）Hankson的趣味题

$$\begin{gathered} \because lcm(a,b)\times gcd(a,b)=a\times b \\ \therefore lcm(x,c)=d\iff d\times gcd(x,c)=x\times c \end{gathered}$$（把$lcm(a,b)$换成$d$）

至于为啥枚举因数

因为

$lcm(x,b)\times \gcd (x,b)=x\times b$

$lcm(x,b)=\frac{x\times b}{\gcd (x,b)}=x\times k_1$

故 $x$ 一定是 $lcm(x,b)$ 的因数。

复杂度 $O(\sqrt{n})$ 。

int a, b, c, d; int ans; int gcd(int a, int b){ return b ? gcd(b, a % b) : a; } int t; int main() { scanf("%d", &t); while(t -- ){ ans = 0; scanf("%d%d%d%d", &a, &b, &c, &d); for(int x = 1, y; x * x <= d; ++ x){ if(d % x)continue; if(gcd(x, a) == b && d * gcd(x, c) == x * c) ans ++ ; y = d / x;//另一个约数 if(x == y)continue; if(gcd(y, a) == b && d * gcd(y, c) == y * c) ans ++ ; } printf("%d\n", ans); } return 0; }

三、互质与欧拉函数

定义

$\forall a,b\in N$若$gcd(a,b)=1$,则称a,b互质

对于三个数或更多的数，把$gcd(a,b,c)=1$称之为a,b,c互质 把$gcd(a,b)=gcd(a,c)=gcd(b,c)=1$称之为a,b,c两两互质。

欧拉函数

$1\cdots N$ 中与 $N$ 互质的数的个数，被称为欧拉函数，记作 $\phi (N)$（phi，读作 fài 大写 $\Phi$ ，小写$\phi$，$\phi$好看）

由算数基本定理得 $$N=p_1^{k_1}\times p_2^{k_2}\times p_3^{k_3}\times \cdots p_m^{k_m}$$ 所以$$\varphi (N)=N\times \frac{p_1-1}{p_1}\times \frac{p_2-1}{p_2}\times \cdots \times \frac{p_m-1}{p_m}=N\times {\Pi }_{质数p|N}(1-\frac{1}{p})$$

其中，如果 $p$ 是素数,则$\phi (p)=p(1-\frac{1}{p})=p-1$。

三种方法求欧拉函数

①直接求小于或等于n,且与n互质的数个数（求[1,n]中所有数的欧拉函数时间复杂度：$O(n\sqrt{n})$）

②求[1,n]之间每个数的质因数的个数（求[1,n]中所有数的欧拉函数时间复杂度：$O(nlogn)$）

③线性筛欧拉函数求[1,n]之间每个数的质因数的个数（求[1,n]中所有数的欧拉函数时间复杂度：$O(n)$）

第三种方法的证明

#include<cstdio> #include<cmath> #include<algorithm> #include<iostream> #include<cstring> using namespace std; typedef long long ll; const int N = 500007, M = 50007, INF = 0x3f3f3f3f; const double eps = 1e-6; int n, m; //欧拉函数，在分解质因数的同时求得欧拉函数 //①直接求小于或等于n,且与n互质的数个数: inline int euler_one(int n) { int ans = n; for(int i = 2; i * i <= n; ++ i){ if(n % i == 0){ ans = ans / i * (i - 1); while(n % i == 0)n /= i; } } if(n > 1)ans = ans / n * (n - 1); return ans; } //②筛选模板:求[1,n]之间每个数的质因数的个数 int euler[N]; inline int euler_all(int n) { memset(euler, 0, sizeof euler); euler[1] = 1; for(int i = 2; i <= n; ++ i){ if(!euler[i]){ for(int j = i; j <= n; j += i){ if(!euler[j]) euler[j] = j;//等同于求一个欧拉函数时的int ans = n; euler[j] = euler[j] / i * (i - 1); } } } } //线性筛欧拉函数建立在线性筛素数的基础之上 //重要性质： //若i % p = 0，p是素数，那么φ(i * p) = φ(i) * p //若i % p != 0,p是素数，那么φ(i * p) = φ(i) * (p - 1) int vis[N]; int prime[N], phi[N]; int sum; void euler(int n) { memset(vis, 0, sizeof vis); int cnt = 0; for(int i = 2; i <= n; ++ i){ if(vis[i] == 0){//如果i是质数 vis[i] = i; prime[ ++ cnt] = i; phi[i] = i - 1; } //给当前的数i乘上一个质因子 for(int j = 1; j <= cnt ; ++ j){ if(prime[j] > vis[i] || prime[j] > n / i)break; vis[i * prime[j]] = prime[j];//根据性质4，5，p^2 | n -> * (p - 1) phi[i * prime[j]] = phi[i] * (i % prime[j] ? prime[j] - 1 : prime[j]); if(i % prime[j] == 0)break; } } } int main() { scanf("%d", &n); for(int i = 1; i <= n; ++ i) cout << euler_one(i) << " "; puts(""); euler_all(n); for(int i = 1; i <= n; ++ i) printf("%d ", euler[i]); puts(""); getphi(); phi[1] = 1; for(int i = 1; i <= n; ++ i) printf("%d ", phi[i]); puts(""); return 0; }

积性函数

​ 如果当 $a,b$ 互质时，满足$f(ab)=f(a)\times f(b)$的函数 $f$ 称为积性函数。（我们是根据欧拉函数的性质2人为地规定拥有这种性质的函数都是积性函数）

欧拉函数性质

$\forall n>1,1\cdots n$中与n互质的数的和为$n\times \phi (n)/2$若$a,b$互质，则$\varphi (ab)=\phi (a)\times \phi (b)$

因为$gcd(n,x)=gcd(n,n-x)$，所以与n不互质的数$x,n-x$成对出现，平均值为 $\frac{n}{2}$ ，因此与n互质的数的平均值也是 $\frac{n}{2}$ ，进而得到性质1。根据欧拉函数的计算式，对$a，b$分解质因数，直接可得性质2。

若 $f$ 是积性函数，且在算数基本定理中 $n={\Pi }_{i=1}^m{p}_i^{c_i}$，则$f(n)={\Pi }_{i=1}^{m}f(p_i^{c_i})$。设 $p$ 为质数，若 $p|n$ 且 $p^2|n$ , 则 $\phi (n)=\phi (\frac{n}{p})\times p$。（$p|n$，p整除与n，也就是说 $p$ 是 $n$ 的因数）设 $p$ 为质数，若 $p|n$ 且$p^2\nmid n$,则 $\phi (n)=\phi (\frac{n}{p})\times (p-1)$。${\sum }_{d|n}\phi (d)=n$。

注：性质$4$ ~ $6$，只是欧拉函数的性质，并非所有的积性函数都满足。

由积性函数还可以延伸出狄利克雷卷积，莫比乌斯反演以及一系列相关的快速求和问题，有缘再学。

（积性函数求和问题的一种筛法）

luogu P2158 [SDOI2008]仪仗队 / AcWing 201. 可见的点

首先我们将原图从$(1,1)$到$(n,n)$​重新标号$(0,0)$到$(n-1，n-1)$

分析题目可知，当$n=1$​时，显然答案是 $0$​，特判断即可

我们考虑 $n\ne 1$的情况，首先$(0,1),(1,0),(1,1)$这三个点是一定能看到的

考虑剩余的点

对于任意的点$(x,y)$，$2\le x,y\le n-1$，若不被其它的点挡住必定满足$gcd(x,y)=1$。

证明：

上述证明链接

我们使用线性筛欧拉函数求解即可。

#include<cstdio> #include<cmath> #include<algorithm> #include<iostream> #include<cstring> using namespace std; typedef long long ll; const int N = 50007, M = 50007, INF = 0x3f3f3f3f; const double eps = 1e-6; int n, m; int vis[N]; int prime[N], phi[N]; int sum; void euler(int n) { memset(vis, 0, sizeof vis); int cnt = 0; for(int i = 2; i <= n; ++ i){ if(vis[i] == 0){//如果i是质数 vis[i] = i; prime[ ++ cnt] = i; phi[i] = i - 1; } //给当前的数i乘上一个质因子 for(int j = 1; j <= cnt ; ++ j){ if(prime[j] > vis[i] || prime[j] > n / i)break; vis[i * prime[j]] = prime[j];//根据性质4，5，p^2 | n -> * (p - 1) phi[i * prime[j]] = phi[i] * (i % prime[j] ? prime[j] - 1 : prime[j]); //if(i % prime[j] == 0)break; } } } int main() { scanf("%d", &n); if(n == 1) puts("0") , exit(0); n --; euler(n); sum = 0; for(int i = 2; i <= n; ++ i) sum += phi[i]; int ans = 3 + 2 * sum; printf("%d\n", ans); return 0; }