acwing算法全总结-数学知识

快速幂

原题链接：快速幂
ac代码：

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
LL qmi(int a,int b,int p)
{LL res=1%p;while(b)//这里本应该分两次进行，不过只有一次询问{if(b&1)res=res*a%p;//不断得出结果并直接相乘a=a*(LL)a%p;//为了积累下一次幂b>>=1;}return res;
}
int main(){int n;cin>>n;while(n--){int a,b,p;cin>>a>>b>>p;printf("%d\n",qmi(a,b,p));}return 0;
}

这里对方法主题进行逐句分析：

LL res=1%p;

这里为什么要%p呢？
我们可以考虑这个情况：当p=1，b=0时，无论a取何值，循环都不会进入，那么如果这里不对q求余，那么res=1，可是正确答案为res=0；
下面对主要部分做解释：

while(b)//这里本应该分两次进行，不过只有一次询问{if(b&1)res=res*a%p;//不断得出结果并直接相乘a=a*(LL)a%p;//为了积累下一次幂b>>=1;}

那什么是快速幂呢？这里给出一个问题：求$$(a^b)modp;$$
如果这里b的数据范围是1e9，计算1e9次，那么会爆tle，所以我们引入了快速幂，快速幂是基于二进制对于算式的优化：
通过优化，我们将o（n）的时间复杂度优化为log（n），
那么我们对这个代码就基本理解了：
if(b&1)res=res*a%p;//不断得出结果并直接相乘
a=a**(LL)a%p;//为了积累下一次幂
b>>=1;
如果b的二进制最小位为1，那么进入进行计算，比如8是100，那么第一位不计算，a在下一句进行累加取余，b去掉最小位，第二位不计算，a继续累乘取余,在第三位进行乘。每次的分步取余是为了防止结果溢出，防止结果错误。

同时注意！res和a都要开long long不然数据过大会溢出

质数筛

题目链接:质数筛线性筛法
ac代码：

#include<iostream>
#include<algorithm>
//https://www.bilibili.com/video/BV1LR4y1Z7pm/?spm_id_from=333.337.search-card.all.click&vd_source=436ccbb3a8f50110aa75654f38e35672
//链接到b站视频
using namespace std;
const int N=1000010;
int primes[N],cnt;
bool st[N];
void get_primes(int n){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%primes[j]==0)break;}}
}
int main(){int n;cin>>n;get_primes(n);cout<<cnt<<endl;return 0;
}

朴素筛法时间复杂度很大，我们加以优化，只筛掉质数的倍数，会将时间复杂度降到nloglogn，再次优化，引入欧拉筛，将时间复杂度降低到o（n）

那么欧拉筛为什么能将质数筛优化到线性呢？因为它每个数只筛一次，而无论是埃式筛还是朴素筛，它在筛去的过程中都有重复
下面我们看代码：

void get_primes(int n){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%primes[j]==0)break;}}
}

if(!st[i])primes[cnt++]=i; 每次把质数存在primes数组中，然后开始循环遍历数组，每一次把primes[j]*i筛掉，也就是被它的最小质因子筛掉，每次只筛一个，不重复，所以在o（n）的时间内得出结果。
那么这一句呢？ ** if(i%primes[j]==0)break;**，这样做的目的是避免重复筛选，即在筛选过程中，只需要考虑能整除当前数 i 的最小质数。因为如果存在一个能整除 i 的质数，那么在之后的迭代中，i 会被标记为非质数，因此不需要再考虑更大的质数能否整除 i。