简单数论

竞赛 / 算法 / 蓝桥杯 / 专题学习
Word count: 2.1k   |   Reading time≈ 9 min

简单数论

模运算

  • 定义：模运算为a除以m的余数，记为a mod m，有a mod m = a % m。

  • 模运算是大数运算中的常用操作。

  • 如果一个数太大，无法直接输出，或者不需要直接输出，可以把它取模后，缩小数值再输出。

  • Python虽然能直接计算大数，不用担心数据溢出，但是大数乘法太耗时，所以也常用取模来缩小数值。

  • 一个简单应用，判断奇偶：a%2 == 0，a是偶数；a%2 == 1，a是奇数

刷题统计解法代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
// 刷题统计 
using ll = long long;
ll a, b, n, ans;

int main() {
	cin>>a>>b>>n;
	ll sum = a*5+2*b;
	ll ans = (n/sum)*7;
	ll r = n%sum;
	if(r<=a*5){
		ans += r/a+(r%a?1:0);// 多的部分也要用1天来完成 
	}else{
		ans += (r-a*5)/b+((r-a*5)%b?1:0);
		ans += 5;
	}
	cout<<ans;
	return 0;
}

快速幂

  • 幂运算an，当n很大时，如果一个个地乘，时间是O(n)的，速度很慢，此时可以用快速幂，在O(logn)的时间内算出来。

  • 快速幂的一个解法：分治法，算a2，然后再算(a2) 2，…，一直算到an，代码也容易写。

  • 标准的快速幂：用位运算实现。

  • 基于位运算的快速幂，原理是倍增。

快速幂原理

image-20230404191246938

快速幂解法代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;
// 快速幂
using ll = long long;
ll b, p, k;

ll fastPow(ll b, ll p, ll k){
	ll res = 1;
	b %= k; // 防止下方res*b越界 
	while(p){// p为次数 
		if(p&1)res = (res*b)%k;
		b = b*b%k;// 对应于a^1,a^2,a^3…… 其中的指数代表的是n二进制中第几位的1（如：1011）
		p = p>>1;// 右移一位 
	}
	return res;
}

int main() {
	cin>>b>>p>>k;
	cout<<fastPow(b, p, k);
	return 0;
}

RSA解密

实质就是快速幂的计算——由于数据太大，因此建议使用Python处理，思路都是一致的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# lanqiao-603-附
n = 1001733993063167141
d = 212353
c = 20190324
p = 891234941
q = 1123984201
temp = (p-1)*(q-1)
now = 0
for i in range(2, n+1):
    now = i*temp+1
    if(now%d==0):
        print(now//d)# 输出e
        break

# 快速幂计算
def fastPow(a, n, mod):
    res = 1
    a %= mod
    while(n):
        if(n&1):res = (res*a)%mod
        a = a*a%mod
        n = n>>1
    return res
print(fastPow(c, now//d, n))

GCD：定义、性质

1、最大公约数Greatest Common Divisor(GCD)：整数a和b的GCD是指能同时整除a和b的最大整数，记为gcd(a, b)。由于-a的因子和a的因子相同，因此gcd(a, b) = gcd(|a|, |b|)。编码时只关注正整数的最大公约数。

2、性质：

（1）gcd(a, b) = gcd(a, a+b) = gcd(a, k·a+b)

（2）gcd(ka, kb) = k·gcd(a, b)

（3）定义多个整数的最大公约数：gcd(a, b, c) = gcd(gcd(a, b), c)。

（4）若gcd(a, b) = d，则gcd(a/d, b/d) = 1，即a/d与b/d互素。这个定理很重要。

（5）gcd(a+cb, b) = gcd(a, b)

手写gcd代码

  • 手写gcd函数，常用欧几里得算法。

  • 辗转相除法求gcd：gcd(a, b) = gcd(b, a mod b)

  • 这是最常用的方法，极为高效。

  • 设a > b，辗转相除法的计算复杂度为O((log2a)3)。

示例代码：
1
2
3
4
5
6
7
8
9
10
11
12
#include<bits/stdc++.h>
using namespace std;
int gcd(int a, int b){ 	return b? gcd(b, a%b):a; }// 递归实现
int main(){
    cout<<gcd(15, 81)<<"\n";    // 输出  3
    cout<<gcd(0, 44)<<"\n";     // 输出  44
    cout<<gcd(0, 0)<<"\n";      // 输出  0
    cout<<gcd(-6, -15)<<"\n";   // 输出  -3
    cout<<gcd(-17,289)<<"\n";   // 输出  -17
    cout<<gcd(17,-289)<<"\n";   // 输出  17
    return 0;
}

LCM：定义、性质

1、最小公倍数LCM（the Least Common Multiple）。

2、a和b的最小公倍数lcm(a, b)，从算术基本定理推理得到。

3、算术基本定理：任何大于1的正整数n都可以唯一分解为有限个素数的乘积：n = p1c1p2c2…pmcm，其中ci都是正整数，pi都是素数且从小到大。

4、推导LCM：

image-20230404225810555

1
2
3
4
5
6
7
8
9
设：a = p1^c1*p2^c2...pm^cm，b = p1^f1*p2^f2...pm^fm
    
那么：gcd(a, b) = p1^min{c1,f1}*p2^min{c2,f2}...pm^min{cm,fm}

lcm(a, b) = p1^max{c1,f1}*p2^max{c2,f2}...pm^max{cm,fm}

推出：gcd(a, b)*lcm(a, b) = a*b

即：  lcm(a, b) = a*b/gcd(a, b) = a/gcd(a, b)*b。

lcm()手写代码

1
2
3
int lcm(int a, int b){    //需要的时候把int改成long long  
   return a / gcd(a, b) * b;  //先做除法再做乘法，防止先做乘法溢出
}

素数的判断

  • 素数定义：只能被1和自己整除的正整数。注：1不是素数，最小素数是2。

  • 判断一个数n是不是素数：当n ≤ 1014时，用试除法；n > 1014时，试除法不够用，需要用高级算法，例如Miller_Rabin算法。

试除法
1
2
3
4
5
6
bool is_prime(long long n){
     if(n <= 1)   return false;         //1不是素数
     for(long long i=2; i <= sqrt(n); i++)  
         if(n % i == 0)  return false;  //能整除，不是素数
     return true;          //n=2时返回true
}

范围[2, n\sqrt{n}]内有多少个素数？在1百万以内，约有7.8万个素数；在1亿以内，约有576万个素数。

素数筛

  • 素数的筛选：给定n，求2~n内所有的素数。

  • 一个个地判断很慢，所以用“筛子”筛所有的整数，把非素数筛掉，剩下的就是素数。

  • 常用两种筛法：埃氏筛、欧拉筛。

埃氏筛

image-20230405011722403

解法代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<bits/stdc++.h>
using namespace std;
// 埃氏筛
const int N = 1e3+10;
int prime[N];// 存储质数 
bool bprime[N];// true标记不是质数 
int cnt;
void getPrime(int n){
	memset(bprime, false, sizeof(bprime));
	bprime[0] = bprime[1] = true;
	for(int i=2;i<=n;++i){
		if(!bprime[i]){// 为质数 
			prime[cnt++] = i; // 存储质数 
			for(int j=i*2;j<=n;j+=i){// 去除质数i的倍数 
				bprime[j] = true;
			}
		}
	} 
}

int main() {// 测试 
	int n;
	cin>>n;
	getPrime(n);
	for(int i=0;i<cnt;++i){
		cout<<prime[i]<<" ";
	}
	return 0;
}

欧拉筛

但是埃氏筛法的缺点：例如6会被3整除，6会被2整除，会被筛两次，所以我们再给出欧氏线性筛法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
using namespace std;
// 欧拉筛 
const int N = 1e3+10;
int prime[N];
bool bprime[N];// true标记不是质数,表示被筛掉 
int cnt; 

void getPrime(int n){
	memset(bprime, false, sizeof(bprime));
	for(int i=2;i<=n;++i){
		if(!bprime[i]){// 是质数 
			prime[cnt++] = i;
		}
		for(int j=0;j<cnt&&i*prime[j]<=n;++j){// 根据当前的prime数组线性地去除非质数 
			bprime[i*prime[j]] = true;// 标记不是质数,表示被筛掉
			if(i%prime[j]==0)break; 
		} 
	}
}

int main() {
	int n;
	cin>>n;
	getPrime(n);
	for(int i=0;i<cnt;++i){
		cout<<prime[i]<<" ";
	}
	return 0;
}

分解质因子

image-20230405021119535

唯一分解定理与约数定理

image-20230405102524542

分类乘法计数原理

分类乘法计数原理是指：如果一个任务可以分解为多个独立的子任务，且每个子任务都有m种不同的方式完成，那么完成整个任务的总方式数就是每个子任务方式数的乘积（即m的n次方，其中n为子任务的数量）。这个原理也叫做乘法原理。

例如，假设有两个任务A和B，完成任务A有3种不同的方式，完成任务B有4种不同的方式。那么完成这两个任务的总方式数就是3 x 4 = 12种。如果还有一个任务C，完成任务C有2种不同的方式，那么完成这三个任务的总方式数就是3 x 4 x 2 = 24种。

这个原理常常用于计算排列和组合问题，求解方法通常是将任务分解为子任务，并根据问题要求进行分类。

  • Copyright： Copyright is owned by the author. For commercial reprints, please contact the author for authorization. For non-commercial reprints, please indicate the source.
  • Copyrights © 2023-2024 Guijie Wang
  • Visitors: | Views:

请我喝杯咖啡吧~

支付宝
微信