第四期 简单数论
冲刺蓝桥杯省一模板大全来啦 ~
蓝桥杯4月8号就要开始了 ~
距离蓝桥杯省赛倒数第3天
还没背熟模板的伙伴们背起来
真题千千万万遍,蓝桥省一自然现!
日更3000里,蓝桥眷顾你
暴力出奇迹,打表过样例
祝大家4月8号蓝桥杯上岸 ~
不清楚蓝桥杯考什么的点点下方
考点秘籍
蓝桥杯竞赛干货
算法竞赛字符串常用操作总结!!!
往期回顾
蓝桥杯上岸每日N题第一期(一)!!!
蓝桥杯上岸每日N题第一期(二)!!!
蓝桥杯上岸每日N题第一期(三)!!!
蓝桥杯上岸每日N题第二期(一)!!!
蓝桥杯上岸每日N题第三期(一)!!!
蓝桥杯上岸必刷专题
蓝桥杯上岸必刷!!!(日期专题+保姆级教学)
蓝桥杯上岸必刷!!!(字符串专题)
蓝桥杯上岸必刷!!!(模拟/枚举专题)
想背纯享模版的伙伴们点点下方
蓝桥杯省一你一定不能错过的模板大全(第一期)
蓝桥杯省一你一定不能错过的模板大全(第二期)
蓝桥杯省一你一定不能错过的模板大全(第三期)
想背注释模版的伙伴们点点下方
蓝桥杯必背第一期
蓝桥杯必背第二期
蓝桥杯上岸必背!!! (第三期 DP)
蓝桥杯上岸必背!!!(第四期DFS)
蓝桥杯上岸必背!!!(第五期BFS)
蓝桥杯上岸必背!!!(第六期树与图的遍历)
蓝桥杯上岸必背!!!(第七期最短路算法)
想看JavaB组填空题的伙伴们点点下方
填空题
前言
考虑到部分同学觉得题解版背模板觉得比较不方便,整理纯模板放便大家背 ~
题解也被我单独切出来,需要直接点击查看即可,是不是很贴心
质数
试除法判定质数
题解
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++){
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");
}
}
}
分解质因数
题解
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);
}
}
if(n>1)System.out.println(n+" "+1);
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);
}
}
}
筛质数
朴素筛
O(nlogn)
耗时:850ms
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;
}
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);
}
}
埃氏筛法(朴素筛优化版)
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);
}
}
线性筛法(推荐)
耗时: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;
}
*/
快速幂
快速幂
题解
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
求组合数 I
题解
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]);
}
}
}
看到这里,不妨点个关注
真题千千万万遍,蓝桥省一自然现!
牛逼!!!!!!!!
慎终追远,勇毅前行!