目录
- 一、约数
- 定义
- 算术基本定理的推论
- 求NNN的正约数集合 - 试除法
- 求1~N每个数的正约数集合 - 倍数法
- AcWing198. 反素数
- 二、最大公约数
- 最大公约数与最大公倍数
- 更相减损术
- luogu P1072 (NOIP2009)Hankson的趣味题
- 三、互质与欧拉函数
- 三种方法求欧拉函数
- 积性函数
- 欧拉函数性质
- luogu P2158 [SDOI2008]仪仗队 / AcWing 201. 可见的点
声明:
本系列博客是《算法竞赛进阶指南》+《算法竞赛入门经典》+《挑战程序设计竞赛》的学习笔记,主要是因为我三本都买了按照《算法竞赛进阶指南》的目录顺序学习,包含书中的少部分重要知识点、例题解题报告及我个人的学习心得和对该算法的补充拓展,仅用于学习交流和复习,无任何商业用途。博客中部分内容来源于书本和网络(我尽量减少书中引用),由我个人整理总结(习题和代码可全都是我自己敲哒)部分内容由我个人编写而成,如果想要有更好的学习体验或者希望学习到更全面的知识,请于京东搜索购买正版图书:《算法竞赛进阶指南》——作者李煜东,强烈安利,好书不火系列,谢谢配合。
下方链接为学习笔记目录链接(中转站)
学习笔记目录链接
ACM-ICPC在线模板
一、约数
定义
若整数n除以整数d的余数为0,即d能整除n,则称 d\tt dd 是 n的约数,n是d的倍数,记为 d∣n\tt d|nd∣n
算术基本定理的推论
由算数基本定理得正整数N可以写作N=p1C1×p2C2×p3C3⋯×pmCmN=p_1^{C_1}\times p_2^{C_2} \times p_3^{C_3} \cdots \times p_m^{C_m}N=p1C1×p2C2×p3C3⋯×pmCm
N的正约数个数为(ΠΠΠ是连乘积的符号,类似∑∑∑)
(c1+1)×(c2+1)×⋯(cm+1)=Πi=1m(ci+1)(c_1+1)\times (c_2+1)\times \cdots (c_m+1)=\Pi_{i=1}^{m}(ci+1)(c1+1)×(c2+1)×⋯(cm+1)=Πi=1m(ci+1)
N的所有正约数和为
(1+p1+p12+⋯+p1c1)×⋯×(1+pm+pm2+⋯+pmcm)=∏i=1m(∑j=0ci(pi)j)(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)(1+p1+p12+⋯+p1c1)×⋯×(1+pm+pm2+⋯+pmcm)=i=1∏m(j=0∑ci(pi)j)
求NNN的正约数集合 - 试除法
约数总是成对出现,所以只需要枚举到n\sqrt{n}n即可。(除了完全平方数,只有一个n\sqrt{n}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的约数个数上界为2n\tt 2\sqrt{n}2n
求1~N每个数的正约数集合 - 倍数法
时间复杂度为O(nlogn)O(nlogn)O(nlogn)(每一个约数为O(1)O(1)O(1)总共nlognnlognnlogn个)
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中每个数的约数的总和大概为NlogNNlogNNlogN。
AcWing198. 反素数
二、最大公约数
最大公约数与最大公倍数
最多O(logn)O(logn)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;//先除后乘,以免溢出
}
∀a,b∈N,gcd(a,b)∗lcm(a,b)=a∗b;\forall a, b \in N,gcd(a, b) * lcm(a, b) = a * b;∀a,b∈N,gcd(a,b)∗lcm(a,b)=a∗b;
更相减损术
∀a,b∈N,a>b,有gcd(a,b)=gcd(b,a−b)=gcd(a,a−b)∀a,b∈N,有gcd(2a,2b)=2gcd(a,b)\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)∀a,b∈N,a>b,有gcd(a,b)=gcd(b,a−b)=gcd(a,a−b)∀a,b∈N,有gcd(2a,2b)=2gcd(a,b)
luogu P1072 (NOIP2009)Hankson的趣味题
∵lcm(a,b)×gcd(a,b)=a×b∴lcm(x,c)=d⇔d×gcd(x,c)=x×c\because lcm(a,b)\times gcd(a,b)=a\times b\\ \therefore lcm(x,c)=d\Leftrightarrow d\times gcd(x,c)= x \times c∵lcm(a,b)×gcd(a,b)=a×b∴lcm(x,c)=d⇔d×gcd(x,c)=x×c(把lcm(a,b)lcm(a, b)lcm(a,b)换成ddd)
至于为啥枚举因数
因为
lcm(x,b)×gcd(x,b)=x×blcm(x,b)\times \gcd(x,b)=x\times blcm(x,b)×gcd(x,b)=x×b
lcm(x,b)=x×bgcd(x,b)=x×k1lcm(x,b)=\cfrac{x\times b}{\gcd(x,b)}=x\times k_1lcm(x,b)=gcd(x,b)x×b=x×k1
故 xxx 一定是 lcm(x,b)lcm(x,b)lcm(x,b) 的因数。
复杂度 O(n)O(\sqrt {n})O(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;
}
三、互质与欧拉函数
定义
∀a,b∈N∀a,b∈N∀a,b∈N若gcd(a,b)=1gcd(a,b)=1gcd(a,b)=1,则称a,b互质
对于三个数或更多的数,把gcd(a,b,c)=1gcd(a,b,c)=1gcd(a,b,c)=1称之为a,b,c互质
把gcd(a,b)=gcd(a,c)=gcd(b,c)=1gcd(a,b)=gcd(a,c)=gcd(b,c)=1gcd(a,b)=gcd(a,c)=gcd(b,c)=1称之为a,b,c两两互质。
欧拉函数
1⋯N1⋯N1⋯N 中与 NNN 互质的数的个数,被称为欧拉函数,记作 φ(N)φ(N)φ(N)(phi,读作 fài 大写 ΦΦΦ ,小写φφφ,φφφ好看)
由算数基本定理得
N=p1k1×p2k2×p3k3×⋯pmkmN= p_{1}^{k_{1}} \times p_{2}^{k_{2}} \times p_{3}^{k_{3}} \times \cdots \ p_{m}^{k_{m}}N=p1k1×p2k2×p3k3×⋯ pmkm
所以ϕ(N)=N×p1−1p1×p2−1p2×⋯×pm−1pm=N×Π质数p∣N(1−1p)\phi(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})ϕ(N)=N×p1p1−1×p2p2−1×⋯×pmpm−1=N×Π质数p∣N(1−p1)
其中,如果 ppp 是素数,则φ(p)=p(1−1p)=p−1φ( p) =p(1- \frac{1}{p}) = p-1φ(p)=p(1−p1)=p−1。
三种方法求欧拉函数
①直接求小于或等于n,且与n互质的数个数(求[1,n]中所有数的欧拉函数时间复杂度:O(nn)O(n\sqrt{n})O(nn))
②求[1,n]之间每个数的质因数的个数(求[1,n]中所有数的欧拉函数时间复杂度:O(nlogn)O(nlogn)O(nlogn))
③线性筛欧拉函数求[1,n]之间每个数的质因数的个数(求[1,n]中所有数的欧拉函数时间复杂度:O(n)O(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,ba,ba,b 互质时,满足f(ab)=f(a)×f(b)f(ab)=f(a)\times f(b)f(ab)=f(a)×f(b)的函数 fff 称为积性函数。(我们是根据欧拉函数的性质2人为地规定拥有这种性质的函数都是积性函数)
欧拉函数性质
- ∀n>1,1⋯n\forall n > 1 , 1\cdots n∀n>1,1⋯n中与n互质的数的和为n×φ(n)/2n\times φ(n) / 2n×φ(n)/2
- 若a,ba,ba,b互质,则ϕ(ab)=φ(a)×φ(b)\phi(ab)=φ(a)\times φ(b)ϕ(ab)=φ(a)×φ(b)
因为gcd(n,x)=gcd(n,n−x)gcd(n, x) = gcd(n, n - x)gcd(n,x)=gcd(n,n−x),所以与n不互质的数x,n−xx,n - xx,n−x成对出现,平均值为 n2\frac{n}{2}2n ,因此与n互质的数的平均值也是 n2\frac{n}{2}2n ,进而得到性质1。根据欧拉函数的计算式,对a,ba,ba,b分解质因数,直接可得性质2。
- 若 fff 是积性函数,且在算数基本定理中 n=Πi=1mpicin=\Pi_{i=1}^{m} p_i^{c_i}n=Πi=1mpici,则f(n)=Πi=1mf(pici)f(n) = \Pi_{i=1}^{m} f(p_i^{c_i})f(n)=Πi=1mf(pici)。
- 设 ppp 为质数,若 p∣np|np∣n 且 p2∣np^2|np2∣n , 则 φ(n)=φ(np)×pφ(n) = φ( \frac{n}{p})\times pφ(n)=φ(pn)×p。(p∣np|np∣n,p整除与n,也就是说 ppp 是 nnn 的因数)
- 设 ppp 为质数,若 p∣np|np∣n 且p2∤np^2 \not| \ np2∣ n,则 φ(n)=φ(np)×(p−1)φ(n) = φ(\frac{n}{p})\times (p-1)φ(n)=φ(pn)×(p−1)。
- ∑d∣nφ(d)=n\sum_{d|n}φ(d)=n∑d∣nφ(d)=n。
注:性质444 ~ 666,只是欧拉函数的性质,并非所有的积性函数都满足。
由积性函数还可以延伸出狄利克雷卷积,莫比乌斯反演以及一系列相关的快速求和问题,有缘再学。
(积性函数求和问题的一种筛法)
luogu P2158 [SDOI2008]仪仗队 / AcWing 201. 可见的点
首先我们将原图从(1,1)(1,1)(1,1)到(n,n)(n,n)(n,n)重新标号(0,0)(0,0)(0,0)到(n−1,n−1)(n−1,n−1)(n−1,n−1)
分析题目可知,当n=1n=1n=1时,显然答案是 000,特判断即可
我们考虑 n≠1n≠1n=1的情况,首先(0,1),(1,0),(1,1)(0,1),(1,0),(1,1)(0,1),(1,0),(1,1)这三个点是一定能看到的
考虑剩余的点
对于任意的点(x,y)(x,y)(x,y),2≤x,y≤n−12≤x,y≤n−12≤x,y≤n−1,若不被其它的点挡住必定满足gcd(x,y)=1gcd(x,y)=1gcd(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;
}