二、筛素数
1.朴素筛法求素数
从2到n枚举每个数，删掉其所有的倍数，枚举完之后，没有被删掉的数为质数。
核心模板
int primes[N],cnt; //primes[]存储所有素数 bool st[N]; //st[x]存储x是否被筛掉 void get_primes(int n){ st[0]=st[1]=true; //0和1均不是质数 for(int i=2;i<=n;i++){ if(st[i]) continue; primes[cnt++]=i; for(int j=i+i;j<=n;j+=i){ st[j]=true; } } }
埃氏筛法
int primes[N],cnt; //primes[]存储所有素数 bool st[N]; //st[x]存储x是否被筛掉 void get_primes(int n){ st[0]=st[1]=true; //0和1均不是质数 for(int i=2;i<=n;i++){ if(!st[i]){ primes[cnt++]=i; for(int j=i+i;j<=n;j+=i){ st[j]=true; } } } }
2.线性筛法求素数（O(n)）
核心模板
int primes[N],cnt; //primes[]存储所有素数 bool st[N]; //st[x]存储x是否被筛掉 void get_primes(int n){ st[0]=st[1]=true; //0和1均不是质数 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; } } }
题目链接：868. 筛质数
2.1题目描述
给定一个正整数 n，请你求出 1∼n 中质数的个数。
输入格式
共一行，包含整数 n。
输出格式
共一行，包含一个整数，表示 1∼n 中质数的个数。
数据范围
1≤n≤106
输入样例：
8
输出样例：
2.2思路分析
利用上述模板即可。
2.3代码实现
埃氏筛法
#include <iostream> using namespace std; const int N=1000010; int n,cnt; int primes[N]; bool st[N]; void getPrimes(int n){ for(int i=2;i<=n;i++){ if(!st[i]){ primes[cnt++]=i; for(int j=i+i;j<=n;j+=i){ st[j]=true; } } } } int main(){ cin>>n; getPrimes(n); cout<<cnt; return 0; }
线性筛法
#include <iostream> using namespace std; const int N=1000010; int n,cnt; int primes[N]; bool st[N]; void getPrimes(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[i*primes[j]]=true; if(i%primes[j]==0) break; //此时primes[j]一定是i的最小质因子 } } } int main(){ cin>>n; getPrimes(n); cout<<cnt; return 0; }
三、欧几里得算法
核心思路：a与b的最大公约数等于b与a mod b的最大公约数。
最大公约数和最小公倍数的关系：
下图内容来源：百度百科，侵删。
核心模板
int gcd(int a,int b){ return b?gcd(b,a%b):a; }
题目链接：872. 最大公约数
3.1题目描述
给定 n 对正整数 ai,bi，请你求出每对数的最大公约数。
输入格式
第一行包含整数 n。
接下来 n 行，每行包含一个整数对 ai,bi。
输出格式
输出共 n 行，每行输出一个整数对的最大公约数。
数据范围
1≤n≤105,1≤ai,bi≤2×109
输入样例：
2 3 6 4 6
输出样例：
3 2
3.2思路分析
使用如上欧几里得算法。
3.3代码实现
#include <iostream> using namespace std; int n; int gcd(int a,int b){ return b?gcd(b,a%b):a; } int main(){ cin>>n; while(n--){ int a,b; cin>>a>>b; cout<<gcd(a,b)<<endl; } return 0; }
四、快速幂
核心模板
求m^k mod p，时间复杂度O(logk)。
int qmi(int m,int k,int p){ int res=1%p,t=m; while(k){ if(k&1) res=res*t%p; t=t*t%p; k>>=1; } return res; }
题目一
题目链接：875. 快速幂
4.1题目描述
给定 n 组 ai,bi,pi，对于每组数据，求出 aibi mod pi 的值。
输入格式
第一行包含整数 n。
接下来 n 行，每行包含三个整数 ai,bi,pi。
输出格式
对于每组数据，输出一个结果，表示 aibi mod pi 的值。
每个结果占一行。
数据范围
1≤n≤100000,1≤ai,bi,pi≤2×109
输入样例：
2 3 2 5 4 3 9
输出样例：
4 1
4.2思路分析
利用快速幂算法进行求解：首先预处理出a的次幂的结果，然后将ak拆分成这些预处理结果的组合（将k拆成2的次方的和，即k的二进制表示为1的所有2的次幂），即利用这些预处理的结果来计算ak。
例子：
4.3代码实现
#include <iostream> using namespace std; typedef long long LL; //快速幂，返回a^k%p的结果 int qmi(int a,int k,int p){ LL res=1%p; //存储结果 while(k){ //枚举k的每位数字 if(k&1) res=res*a%p; //如果该位数字为1，则res乘上当前数字代表的二进制中的权重（即2的多少次幂） k>>=1; a=(LL)a*a%p; //a每次翻倍，预处理出当前a的次幂的结果 } return res; } int n; int main(){ cin>>n; while(n--){ int a,k,p; cin>>a>>k>>p; cout<<qmi(a,k,p)<<endl; } return 0; }
题目二
题目链接：876. 快速幂求逆元
4.4题目描述
给定 n 组 ai,pi，其中 pi 是质数，求 ai 模 pi 的乘法逆元，若逆元不存在则输出 impossible。
注意：请返回在 0∼p−1 之间的逆元。
乘法逆元的定义
若整数 b，m 互质，并且对于任意的整数 a，如果满足 b|a，则存在一个整数 x，使得 a / ≡ a * x(mod m)，则称 x 为 b 的模 m 乘法逆元，记为 b−1 (mod m)。
b 存在乘法逆元的充要条件是 b 与模数 m 互质。当模数 m 为质数时，bm−2 即为 b 的乘法逆元。
输入格式
第一行包含整数 n。
接下来 n 行，每行包含一个数组 ai,pi，数据保证 pi 是质数。
输出格式
输出共 n 行，每组数据输出一个结果，每个结果占一行。
若 ai 模 pi的乘法逆元存在，则输出一个整数，表示逆元，否则输出 impossible。
数据范围
1≤n≤105,1≤ai,pi≤2∗109
输入样例：
3 4 3 8 5 6 3
输出样例：
1 2 impossible
4.5思路分析
由题目信息可得到以下化简。
该问题就化简成了求：b * x ≡ 1 (mod p )。x即为所求的逆元。
由费马小定理可知：b^p-1 ≡ 1 (mod p )。所以我们结合上述两个式子可知，x=bp-2。
下图内容来源：百度百科，侵删。
b如果是p的倍数则无解。
原因：如果p是b的倍数，那么p*x也是p的倍数，mod p之后一定等于0，不可能等于1（也就是得满足费马小定理的条件）。
4.6代码实现
#include <iostream> using namespace std; typedef long long LL; //快速幂模板，返回a^k%p int qmi(int a,int k,int p){ LL res=1%p; while(k){ if(k&1) res=res*a%p; k>>=1; a=(LL)a*a%p; } return res; } int n; int main(){ cin>>n; while(n--){ int a,p; cin>>a>>p; int ans=qmi(a,p-2,p); //ans代表所要求的逆元，即ans=a^p-2 if(a%p) cout<<ans<<endl; else cout<<"impossible"<<endl; //无解情况：a%p=0时无解 } return 0; }
