【备战蓝桥杯】2024蓝桥杯赛前突击省一：基础数论篇

2024蓝桥杯赛前突击省一：基础算法模版篇

基础数论算法回顾

判断质数（试除法）

时间复杂度O（sqrt(n)）

static int is_prime(int n){if(n<2) return 0;for (int i=2;i<=n/i;i++){if(n%i==0) return 0;}return 1;
}

质因数分解

时间复杂度O（sqrt(n)）

static Map<Integer,Integer> mp = new TreeMap<>();//TreeMap有序
static void divide(int n){for(int i=2;i<=n/i;i++){int cnt = 0;//java里不能mp[i]++，所以用变量cnt存储，再赋值while(n%i==0){n/=i;cnt++;}mp.put(i,cnt);}if(n>1) mp.put(n,1);
}
//输出
for(Integer key:mp.keySet()){int val = mp.get(key);if(val>0)System.out.println(key+" "+mp.get(key));
}

素数筛

埃氏筛法

求n以内的所有素数

时间复杂度（O（nlogn））

static int[] st;
static int[] primes;
static int cnt;void get_primes(int n){for(int i=2;i<=n;i++){if(st[i]==0){primes[cnt++]=i;for(int j=i+i;j<=n;j+=i)st[j]=1;}}//求素数个数cnt	
}

线性筛

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;}}
}

求约数

时间复杂度 sqrt(n）

	static ArrayList<Integer> yue = new ArrayList<>();   static void solve(int n){for (int i = 1; i <= n/i; i++) {if(n%i==0){yue.add(i);if(n/i!=i)yue.add(n/i);}}Collections.sort(yue);//约数从小到达排}

求组合数

求C（a,b）

用long存！！！

• N 在3000以内（题意不用取模）

    static long[][] C = new long[N][N];static void init(){for (int i = 0; i < N; i++) {for (int j = 0; j <= i; j++) {if(j==0) C[i][j] = 1;else C[i][j] = C[i-1][j] + C[i-1][j-1];//对于要对答案取模的时候，在计算组合数的时候就要取模//else C[i][j] = (C[i-1][j] + C[i-1][j-1])%Mod;}}}

• N在10^8以内、题目说要取模（用逆元求）

  C(a,b) = a!/(b! * (a-b)!) = a! * niyuan(b!) * niyuan((a-b)!)

  由于询问比较多，直接初始化阶乘和阶乘的逆元数组

  递推式：
  n! = (n-1)! * n
1/(n!) = 1/(n-1)! * 1/n,其中1/n = qpow(n,Mod-2)(费马小定理)

    //jiechen[i] = i!static long[] jiechen = new long[N];//jiechenniyuan[i] = “i!的逆元”static long[] jiechenniyuan = new long[N];//初始化阶乘、阶乘的逆元static void init() {jiechen[0] = 1;jiechenniyuan[0] = 1;for(int i=1;i<N;i++) {jiechen[i] = jiechen[i-1] * i%Mod;jiechenniyuan[i] = jiechenniyuan[i-1] * qpow(i, Mod-2)%Mod;}}//C(a,b) = a!/(b! * (a-b)!) = a! * niyuan(b!) * niyuan((a-b)!)static long C(int a,int b) {long res = 1;res = res * jiechen[a]%Mod;res = res * jiechenniyuan[b]%Mod;res = res * jiechenniyuan[a-b]%Mod;return res;}
https://www.acwing.com/activity/content/code/content/5904493/

扩展欧几里得算法

裴蜀定理

• 若a,b是整数,且gcd(a,b)=d，那么对于任意的整数x,y,都有ax+by都一定是d的倍数。（充要的）
  特别地，一定存在整数x,y，使ax+by=d成立。

换句话说：

• 两个整数a,b,方程a*x+b*y=m有解，当且仅当m是gcd(a,b)的倍数（充要）

扩展欧几里得代码：

// 求x, y，使得ax + by = gcd(a, b)
// 扩展欧几里得:求解方程ax+by=gcd(a,b)的解
// x=y′ y=x′−[a/b]*y′
static int x, y;//全局变量，替代引用
int exgcd(int a,int b){if(b==0){x=1,y=0;return a;}int gcd=exgcd(b,a%b);//递归调用int tmp = x;x=y,y=tmp-a/b*y;return gcd;
}//结果说明1.exgcd()的返回值是最大公约数2.最后的（x，y）是方程ax + by = gcd(a,b)的解3.如果exgcd()的结果是1（那么a和b互质，就存在逆元），那么x是a的逆元（x可能是负数，所以答案是getMod(x)）

费马小定理

描述：

如果一个数p是质数，并且a不是p的倍数，那么有a^（p-1） = 1 (mod p)。
除以p同余

等价于：（推荐）

如果一个数p是质数,并且a和p互质（等价于gcd(a,p）=1），那么有a^（p-1） = 1 (mod p)