第八期：简单数论
蓝桥杯热门考点模板总结来啦
~
你绝绝绝绝绝绝对不能错过的常考简单数论模板 
冲刺蓝桥杯省一模板大全来啦 ~
蓝桥杯4月8号就要开始了 
~
距离蓝桥杯省赛倒数第3天
还不清楚简单数论的同学快快看过来！！！
还没背熟模板的伙伴们背起来 
真题千千万万遍，蓝桥省一自然现！ 
日更3000里，蓝桥眷顾你 
祝大家4月8号蓝桥杯上岸 
~
不清楚蓝桥杯考什么的点点下方
考点秘籍
蓝桥杯竞赛干货
算法竞赛字符串常用操作总结！！！
往期回顾
蓝桥杯上岸每日N题第一期(一)！！！
蓝桥杯上岸每日N题第一期(二)！！！
蓝桥杯上岸每日N题第一期(三)！！！
蓝桥杯上岸每日N题第二期(一)！！！
蓝桥杯上岸每日N题第三期(一)！！！
蓝桥杯上岸必刷专题
蓝桥杯上岸必刷！！！(日期专题+保姆级教学)
蓝桥杯上岸必刷！！！(字符串专题)
蓝桥杯上岸必刷！！！(模拟/枚举专题)
想背纯享模版的伙伴们点点下方
蓝桥杯省一你一定不能错过的模板大全(第一期)
蓝桥杯省一你一定不能错过的模板大全（第二期）
蓝桥杯省一你一定不能错过的模板大全（第三期）
想背注释模版的伙伴们点点下方
蓝桥杯必背第一期
蓝桥杯必背第二期
蓝桥杯上岸必背！！！ (第三期 DP)
蓝桥杯上岸必背！！！(第四期DFS)
蓝桥杯上岸必背！！！(第五期BFS)
蓝桥杯上岸必背！！！(第六期树与图的遍历)
蓝桥杯上岸必背！！！(第七期最短路算法)
想看JavaB组填空题的伙伴们点点下方
填空题
前言
简单数论：求质数、最大公约数、快速幂、组合数这些都是算竞必背的储备/技巧。
不单单是只出现在编程题，以前大部分出现在填空题。可见其重要性
简单数论的模板代码量不多，可以直接记，有时间可以理解记忆。 
质数
试除法判定质数
质数定义
质数：所以大于1的自然数
如：2、3、4、5、······
质数的定义：
在大于1的整数中，如果只包含1和其本身这两个约数就被称为质数，或者叫素数。
补充：
所有<=1的整数既不是质数也不是合数
质数和合数是针对所有大于1的数定义的
试除法判定质数
(1)所有不满足>1的筛掉
(2)枚举能被i整除的数
for(int i=2;i<n;i++){
//质数指的是除1和其本身n之外不能被其他数所整除
//这里枚举时从2~n-1即可
if(n%i==0)return false;
}
优化：
从质数的性质出发
d|n-->n|d|n
d能整除n，说明n|d也能整除n。
枚举的终止条件次数减小到 d<=n/d
进一步化简式子：d*d<=n即d<=sqrt(n)
时间复杂度：
枚举次数从n–>sqrt(n)
O(sqrt(n))
推荐写法
d<=n/d;
原因：
(1)d*d<=n
n的最大值为2147483647
当i*i<=n,n接近最大值时：
下一次(i+1)*(i+1)时大于最大值,就会出现溢出错误。
(i+1)x(i+1)就会变为负数,造成结果错误。
(2)d<=sqrt(n)
每次枚举时都需要计算一遍sqrt(n),sqrt()函数比较慢，耗时多，不推荐。
Accode
import java.util.*;
public class Main{
public static boolean primes(int n){
if(n<2)return false;
//不满足定义筛掉
for(int i=2;i<=n/i;i++){
//记住从2开始枚举到根号n结束
if(n%i==0)return false;
}
return true;
}
public static void main(String []args){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
while(n-->0){
int a=sc.nextInt();
if(primes(a))System.out.println("Yes");
else System.out.println("No");
}
}
}
分解质因数
分析
质因子：底数为质数
当枚举到i时，意味着把2~i-1的质因子都除干净了。
也就意味着i不包含从2~i-1的质因子
那么n是i的倍数,并且n、i中不包含2~i-1之间的所有质因子
那么i一定是质数,不是合数
优化
性质：
n中最多只包含一个大于sqrt(n)的质因子
证：
假设n中包含两个大于sqrt(n)的质因子,两个相乘必定大于n。
所以最多只存在一个大于sqrt(n)的质因子。
时间复杂度
试除法判定质数
试除法判定质数
时间复杂度一定是O(sqrt(n))
分解质因数：
最好情况下是：O(logn)
最坏情况下是：O(sqrt(n))
时间复杂度介于O(logn)~O(sqrt(n)之间,总体优于试除法判定质数。
Accode
import java.util.*;
public class Main{
public static void divide(int n){
for(int i=2;i<=n/i;i++){
if(n%i==0){
//找到质因子
int s=0;
//统计质因子的个数
while(n%i==0){
n/=i;
s++;
}
System.out.println(i+" "+s);
//i表示质数,s表示指数(质因子出现的次数)
}
}
if(n>1)System.out.println(n+" "+1);
//如果最后n大于1，则n为大于sqrt(n)的数。
//特判输出一下即可。
System.out.println();
}
public static void main(String []args){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
while(n-->0){
int a=sc.nextInt();
divide(a);
}
}
}
筛质数
建议听y总顺一遍
朴素筛
从2~n中去枚举每个数，假设当前枚举到的数为P，后面出现是P的倍数的数均删掉，最后剩下的便是不存在倍数关系的质数，统计个数即可。
为什么需要删掉?
因为，假设某个数a是P的倍数，说明这个数除了1和它本身外，还能整除P，与质数的定义相悖，因此a不是质数，需要筛掉。
时间复杂度：O(nlogn)
耗时：850ms
import java.util.*;
public class Main{
static int N=1000010;
static int cnt;
static boolean st[]=new boolean[N];
public static void get_primes(int n) {
for(int i=2;i<=n;i++) {
//从2开始枚举，因为1不是质数
//依次枚举每个数，看是不是质数
if(!st[i])cnt++;
//如果最后没有被标记说明是质数
for(int j=i+i;j<=n;j+=i) {
st[j]=true;
//枚举每个数在2~n中是否存在i的倍数的数
//存在则打上标记，置为true，将他们都筛掉。
}
}
}
public static void main(String []args) {
Scanner scanner=new Scanner(System.in);
int n=scanner.nextInt();
get_primes(n);
System.out.println(cnt);
}
}
埃氏筛法(朴素筛优化版) (必背)
实际上是将筛去质数约束这一轮循环放到if语句中
这样做的好处是：不需要枚举2~n中的每个数
当枚举的n是质数时，将前面与n有倍数约束关系的数字筛掉。
筛掉后下一次就不需要再枚举,只需要枚举质数即可,减少枚举的次数。
时间复杂度：O(nloglogn)
耗时：782 ms
import java.util.*;
public class Main{
static int N=1000010;
static int primes[]=new int[N];
static boolean st[]=new boolean[N];
static int cnt=0;
public static void get_primes(int n){
for(int i=2;i<=n;i++){
if(!st[i]){
primes[cnt++]=i;
//不需要去枚举从2~n-1里的所有数
//当枚举的n是质数时，将前面与n有倍数约数关系的数字筛掉
//这样枚举的时候只需枚举质数即可，减少枚举的次数
for(int j=i+i;j<=n;j+=i)st[j]=true;
}
}
}
public static void main(String []args){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
get_primes(n);
System.out.println(cnt);
}
}
线性筛法(推荐)
n只会被最小质因子筛掉
primes[j]:表示是i的最小质因子
后面用pj同义表示
1.i%pj==0
pj是从前往后去枚举，最先满足条件的一定是最小质因子。
pj一定是i的最小质因子，pj一定是pj*i的最小质因子
2.i%pj!=0
找不到质因子，说明pj一定小于 i的所有质因子。
pj一定小于i的所有质因子，pj一定是pj*i的最小质因子
这样可以通过最小质因子筛掉i中有约束关系的数,剩余的便是质数
耗时：766 ms
import java.util.*;
public class Main{
static int N=1000010;
static int primes[]=new int[N];
static boolean st[]=new boolean[N];
static int cnt=0;
public static void get_primes(int n){
//依次枚举每个数字
for(int i=2;i<=n;i++){
if(!st[i])primes[cnt++]=i;
//如果说当前的i没有没被筛掉则说明他是质数
for(int j=0;primes[j]*i<=n;j++){
st[primes[j]*i]=true;
//存在i倍的关系则把他给筛掉
if(i%primes[j]==0)break;
//说明primes[j]一定是i的最小质因子,筛掉i
}
}
}
public static void main(String []args){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
get_primes(n);
System.out.println(cnt);
}
}
约数
辗转相除法
import java.util.*;
public class Main{
public static int gcd(int a,int b){
while(b!=0){
int c=a%b;
a=b;
b=c;
}
return a;
}
public static void main(String []args){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
while(n-->0){
int a=sc.nextInt();
int b=sc.nextInt();
System.out.println(gcd(a,b));
}
}
}
/*
组合数：C(a，b)
public static long C(long a,long b){
long res=1;
for(int i=a,j=1;j<=b;i--,j++){
res=res*i/j;
if(res>n)return res;
}
return res;
}
*/
快速幂
快速幂
分析
反复平方法
a^k mod p
对k进行拆分
把他进行预处理出来
把k 从一个十进制数拆成若干个二进制数
再将a的幂数相加即可！
怎么加？
观察发现拆开后，后一项等于前一项的平方再%，总共是logk项
借助这一点反复平方直至b为0时,说明此时的k已无可再拆分的数为止。
注意
本题输入数据比较大，java选手需要快读快写！！！
Accode
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.*;
public class Main{
static BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
static PrintWriter pW = new PrintWriter(new OutputStreamWriter(System.out));
public static long qmi(int a,int b,int p) {
long ans=1;
//开long
//反复平方法
while(b>0) {
if((b&1)==1)ans=ans*a%p;
//如果说末位为1则ans=a%p
b>>=1;
//再把这一位给删掉
a=(int)((long)a*a%p);
//反复平方法再取模
}
return ans;
}
public static void main(String []args) throws NumberFormatException, IOException {
int n=Integer.parseInt(bf.readLine());
while(n-->0) {
String s[]=bf.readLine().split(" ");
int a=Integer.parseInt(s[0]);
int b=Integer.parseInt(s[1]);
int p=Integer.parseInt(s[2]);
pW.println(qmi(a,b,p));
}
pW.flush();
}
}
求组合数
求组合数I
分析
递推式：C(a,b)=C(a-1,b)+C(a-1,b-1)
理解：假设我挑出一个苹果
(1)包含该苹果
当前包含该苹果，由于该苹果已经被我选了，还剩a-1件。
所以从剩余的b-1件苹果中选
(2)不包含该苹果
当前不包含该苹果，苹果还剩a-1件。
这a-1件从b件苹果中去选
ACcode
import java.util.*;
public class Main{
static int N=2010;
static int mod=1000000007;
//写成1e9+7会报精度损失
//直接写数字即可
static int c[][]=new int[N][N];
public static void init(){
for(int i=0;i<N;i++){
for(int j=0;j<=i;j++){
if(j==0)c[i][j]=1;
//注意边界情况，从中选0个苹果的方案为1
else c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
//递推式，数字比较大需要取模
}
}
}
public static void main(String []args){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
init();
while(n-->0){
int a=sc.nextInt();
int b=sc.nextInt();
System.out.println(c[a][b]);
}
}
}
看到这里，不妨点个关注 
明后天出考前锦囊，喜欢的同学可以关注一下！！！
暴力出奇迹，打表过样例！！！