数论入门
快速幂
一个最基本的，在数论题中较为常用的算法：
用于处理乘方后数字较大，以至于要使用模数在中途取模的情况
一般有两种写法：
法一：递归
int qp(int 底数,int 指数,int 模数){
if(指数==0)return 1;
if(指数==1)return 底数%模数;//两个特判
int t=qp(底数,指数/2,模数)%模数;//指数分成两半处理
return (((t*t)%模数)*(
指数%2?底数%模数:1//如果指数为奇数，递归后要再乘上一个底数
))%模数;//要养成遍地取模的好习惯
}
法二：位运算
int qpow(int 底数,int 指数,int mod) {
int res=1;//因为是乘法运算，所以初始化结果为1
while(指数>0){
//如果当前指数的最低位是1，则将当前基数乘到结果中
if(指数&1)res=(底数*res)%mod;
// 基数平方，指数右移一位
底数=(底数*底数)%mod;//要养成遍地取模的好习惯
指数>>=1;
}
return res;
}
同学：你怎么用中文写代码啊？
我：C++20早就支持中文了！
同学：啊？！（目瞪口呆）
质数
定义很简单，这里就不再赘述了。
我们重要的是讲如何高效率的筛出指数。
法一：试除
最简单、朴素的算法，从 2 到 \sqrt{n} 逐一枚举是否能整除 n 来判断 n 是否为质数
int cnt=0;int prime[114514];//114514 is a funny number
bool check(int x){
if(x==1) return false;
for(int i=2;i*i<=x;i++){//从2遍历到sqrt(n)
if(x%i==0)return false;
}
return true;
}
int kkksc03(int a){
for(int i=1;i<=a;i++){
if(check(i)){
prime[++cnt]=i;
}
}
}
时间复杂度 O(n\sqrt{n}) 。
空间复杂度 O(n) 。
法二：埃氏筛
从 2 开始遍历，如果一个数没被标记过，那么这个数就是质数，并在范围内把这个质数的所有倍数都标记一遍
注： 1 不是质数，所以要提前标记，或直接从 2 开始遍历
bool vis[114514];
int cnt=0;int prime[114514];//114514 is a funny number
void chen_zhe(int a){
for(int i=2;i<=a;i++){//从2开始遍历
if(!vis[i]){
prime[++cnt]=i;
for(int j=2;j*i<=a;j++){//把倍数标记一遍
vis[j*i]=1;
}
}
}
}
时间复杂度 O(n\ln\ln n) 。
空间复杂度 O(2n) 。
法三：欧拉筛
在埃氏筛的基础上，保证每个数只被自己除以自己最小的除 1 外的因子标记一遍。
bool vis[114514];
int cnt=0;int prime[114514];//114514 is a funny number
void fu_su(int a){
for(int i=2;i<=a;i++){
if(!vis[i])prime[++cnt]=i;
for(int j=1;prime[j]*i<=a;j++){
if(!prime[j])break;
vis[prime[j]*i]=1;
if(i%prime[j]==0)break;
}
}
}
时间复杂度 O(n) 。
空间复杂度 O(2n) 。
同学：你为什么数组都要开114514啊？
我：还不是跟xiaoxiaoxia学的。
GCD与LCM
GCD：最大公约数
LCM：最小公倍数
一些常用性质：
-
\gcd(\gcd(a,b),c)=\gcd(a,\gcd(b,c))
-
维护一个集合的 \gcd 时，每增加一个新的元素 \gcd 要么不变，要么减少（最多减少 log_2 首项 次）。
-
通过上面这个性质，我们知道一个序列的 \gcd 是单调不增的。
-------------------------分----------------割---------------线--------------------------
那么怎么快速求他们呢？
这里就不卖关子了：辗转相除法
这样我们就可以用 O(\log \max(a,b)) 求他们的 \gcd 了！
int gcd(int a,int b){
return b?gcd(b,a%b):a;//当b=0时，递归到边界，gcd就是a
}
具体怎么证明，我也不知道了…
证明就留给大家自己去学习吧，有答案可以发在讨论区哦！
其实作者自己没看懂证明，快去补啊qwq（逃
那么 lcm 怎么求呢？
不难发现 a,b 的最小公倍数就是他们所有的质因子相乘，再除去两者间重复的质因子，而他们的重复的质因子，就是 \gcd(a,b)
于是我们就可以列出公式 :
也就是说，我们在知道 \gcd(a,b) 的情况下，可以 O(1) 求出 lcm(a,b)
int lcm(int a,int b){
return a*b/gcd(a,b);//没错，这两部分代码就是这么短小精悍！
}
还是那句话，LATEX炸了的刷新一下
拜托了qwq
不要老是在评论区发看不见LATEX
猜你想搜：
update:\ \ 2024/7/28\ \ \ 16:14 加了一些 \gcd 常用性质。
update:\ \ 2024/7/28\ \ \ 16:56 加了辗转相除法的证明链接。