简单数论

学习
字数统计: 2.5k   |   阅读时长≈ 11 分钟

简单数论

1. 质数筛

先从最简单的质数开始吧，用优化遍历大小的朴素法或者欧拉筛(线性筛)可以完成，时间复杂度分别是O(n)和O(logn)

1
2
3
4
5
6
7
8
9
10
bool isPrime(int n) {
	// 最小的质数是2
	if(n<=1)
		return false;
	for(int i=2;i<=sqrt(n);i++) {
		if(n%i==0)
			return false;
	}
	return true;
}

2. 进制数拆

比如把任意一个正整数拆成二进制表现的形式，如7=2的2次方+2的1次方+2的0次方

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
vector<int> v;

// n:待拆分十进制数
// m:拆分成多少进制的数
void split(int n,int m) {
	int s=0; // 权
	while(n) {
		if(n%m) {
			cout<<m<<'^'<<s<<'='<<pow(m,s)<<'\n';
			v.push_back(pow(m,s));
		}
		n/=m;
		s++;
	} cout<<endl;
	sort(v.begin(),v.end(),greater<int>());
	for(int i=0;i<v.size();i++) {
		cout<<v[i];
		if(i!=v.size()-1) cout<<"+";
	}
}

3. 分解质因数

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef pair<int,int> PII;

/*
  解题思路: 分解质因数,一边找质因子一边将质因子的值和幂存储起来
 */

const int N=1e5+5;

// p[]:存储质因子,p[cnt]=x,第cnt个质因子是x
// g[]:存储质因子的幂,g[cnt]=y,第cnt个质因子是x,幂是y
// cnt:记录个数
int n,p[N],g[N],cnt; 
int res;

// 分解质因数
void prime_fact(int n) {
	// i*i<=n:枚举优化,从2开始,2是最小的质数
	for(int i=2;i*i<=n;i++) {
		if(n%i==0) cnt++; // i是n的因子,cnt++
		// 计算i的幂
		while(n%i==0) {
			p[cnt]=i;
			g[cnt]++; // 次幂+1
			n/=i;
		}
	}
	// 分解完后如果n>1,说明最终剩下的数字是一个质数,也单独算成质因数
	if(n>1) {
		p[++cnt]=n;
		g[cnt]++;
	}
}

int main() {
	cin>>n;
	prime_fact(n);
	for(int i=1;i<=cnt;i++) {
		printf("质因数: %d, 幂为:%d\n",p[i],g[i]);
	}
	// 按唯一分解定理形式打印
	cout<<n<<"=";
	// 遍历p,g数组
	for(int i=1;i<=cnt;i++) {
		// 打印g[i]次p[i]
		for(int j=1;j<=g[i];j++) {
			cout<<p[i];
			if(j!=g[i]) cout<<"*";
		}	
		if(i!=cnt) cout<<"*";
	}
	return 0;
}

4. 质数筛

4.1. 试除法（枚举优化）

1
2
3
4
5
6
7
bool isPrime(int num) {
    for(int i=2;i<=sqrt(num)) {
        if(num%i==0)
            return false;
    }
    return true;
}
  • 如果要找从 $[1,10000]$ 中的所有质数，时间复杂度很高

4.2. 欧拉筛

image-20230720102317937

  • 算法思想：遍历到 $2$ 的时候，筛掉范围内所有 $2$ 的倍数，到 $3$ 的时候，筛掉所有 $3$ 的倍数，被筛掉的数会被标记为合数，合数不会进入到 $if$ 中扩展其倍数，相当于每个数只被遍历过一次，因而时间复杂度是 $O(n)$，欧拉筛也被称为线性筛
  • 注意：如果计算 $[l,r]$ 之间出现的质数的个数？可以用前缀和的思想；
    当 $n$ 过大时，$i×i$ 容易出现数组越界的错误，即可能 $RuntimeError$，此时要将线性筛中第二个 $for$ 中的$j=i×i$ 改为 $j=i+i$
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef pair<int,int> PII;

/*
  解题思路: 欧拉筛
  先从最小的质数开始,每次在数据范围内将它的倍数标记为合数,那么留下的一定是素数
  
 */

const int N=1e5+5;

int f[N]; // f[i]:记录1~i中所有质数的数量
bool st[N]; // st[i]:i的访问状态
int p[N]; // 存放1~n中所有素数
int idx,n; // idx:找素数迭代器

void get_primes(int n) {
	f[1]=0;
	for(int i=2;i<=n;i++) {
		// 如果i未放问过
		if(!st[i]) {
			f[i]=f[i-1]+1; // 计算前缀和,维护数量
			p[++idx]=i; // 存储素数
			// 如果出现RE,将j=i*i改成j=i+i,这样就不会越界
			// 将i的倍数全部标记为合数,无需遍历
			for(int j=i*i;j<=n;j+=i) st[j]=true;
		} else {
			f[i]=f[i-1]; // 向下传递素数个数
		}
	}
}

int main() {
	cin>>n;
	int l,r;
	cin>>l>>r;
	get_primes(n);
	printf("1~%d 之间的质数分别是:",n);
	for(int i=1;i<=idx;i++) {
		cout<<p[i];
		if(i!=idx) cout<<",";
	} cout<<endl;
	printf("%d~%d 之间存在的质数个数是:%d\n",l,r,f[r]-f[l-1]);
	return 0;
}

5. 最大公约数与最小公倍数

辗转相除法的时间复杂度：近似 $O(max(a,b))$

5.1. 两个数

  • 辗转相除法（欧几里得算法）求解最大公约数，最小公倍数就是两数的成绩除以最大公约数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 求两个数的最大公约数
int GCD(int m,int n) {
	int r;
	while(m%n) {
		r=m%n;
		m=n;
		n=r;
	}
	return n;
}

// 更简单易背的方法
int gcd(int a,int b) {
    return b?gcd(b,a%b):a;
}

// 求两数的最小公倍数
int LCM(int m,int n) {
	return m*n/GCD(m,n);	
}

5.2. n个数

5.2.1. 求公共GCD

  • 求多个数的 $GCD$ 的思路是先求两个数的 $GCD$，再用这个结果与后续的每一个数分别求出 $GCD$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const int N=1e5+5;
int n,a[N];

int gcd(int a,int b) {
	return b==0?a:gcd(b,a%b);
}

int main() {
	cin>>n;
	for(int i=1;i<=n;i++) {
		cin>>a[i];	
	}
	// 通过循环求出公共GCD
	int res=a[1]; 
	for(int i=2;i<=n;i++) {
		res=gcd(res,a[i]);
	}
	return 0;
}
  • 上述求解方法的时间复杂度最坏是 $O(n^2)$，所以数据量比较大时，推荐用下述方法求解公共 $GCD$

  1. 对这组数从大到小排序

  2. 对每两个相邻的数 $A,B$（假设 $A$ 在前，故有 $A>B$），如果 $A=n×B$，则令 $A=B$；否则令 $A=A%B$

  3. 重复上述步骤，直到数组中每个数字都相同，此时这个数就为公共 $GCD$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool cmp(int a,int b) {
	return a>b;
}

int multi_gcd(int a[],int n) {
	sort(a+1,a+1+n,cmp);
	// 直到所有数字相等
	while(a[1]!=a[n]) {
		for(int i=1;i<n;i++) {
			if(a[i]%a[i+1]==0) a[i]=a[i+1];
			else a[i]=a[i]%a[i+1];
		}
		sort(a+1,a+1+n,cmp);
	}
	return a[1];
}

5.2.2. 求公共LCM

  • 同样的，我们可以对这组数据依次求最小公倍数，但是时间复杂度在最坏时达到 $O(n^2)$
1
2
3
4
5
6
7
8
9
10
int gcd(int a,int b) {
	return b==0?a:gcd(b,a%b);
}

int multi_lcm(int a[],int n) {
	int res=a[1];
	for(int i=1;i<=n;i++) {
		res=res*a[i]/gcd(res,a[i]);
	}
}

  • 接下来介绍质因子分解法，如：求 $10,12,4$ 的最小公倍数
    $① 10=2×5,\ ② 12=2×3×3,\ ③4=2×2$
    可见，$2$ 在①②③式中都出现了， $3$ 只在②式中出现， $5$ 只在①式中出现
    所以最小公倍数：$2^3×3^1×5^1=60$，即对每个质因子的最高次幂做乘积得到的就是公共 $LCM$

  • 用这种方法也可以避免遍历时做乘法超出数据类型所能表示的最大范围的情况

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include<bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef pair<int,int> PII;

/*
  解题思路: 求公共LCM
  1) 先用欧拉筛预处理出数据范围内所有质数
  2) 将数组a中的数字依次分解质因数,按照欧拉筛筛出来的质数分解
  3) 用一个map记录所有质因子出现的最小次数(计算GCD)或最大次数(计算LCM)
  4) 枚举map中的质因子及其出现次数乘在一起算出GCD和LCM即可
  
 */

const int N=1e5+5;

int f[N]; // f[i]:记录1~i中所有质数的数量
bool st[N]; // st[i]:i的访问状态
int p[N]; // 存放1~n中所有素数
int idx,n; // idx:找素数迭代器 
map<int,int> m_max; // m_max[i]:对a[i]进行质因数分解后每个质因数的最大次数
int a[N]; 

void get_primes(int n) {
	f[1]=0;
	for(int i=2;i<=n;i++) {
		// 如果i未放问过
		if(!st[i]) {
			f[i]=f[i-1]+1; // 计算前缀和,维护数量
			p[++idx]=i; // 存储素数
			// 如果出现RE,将j=i*i改成j=i+i,这样就不会越界
			// 将i的倍数全部标记为合数,无需遍历
			for(int j=i*i;j<=n;j+=i) st[j]=true;
		} else {
			f[i]=f[i-1]; // 向下传递素数个数
		}
	}
}

void get_facts(int a[]) {
	for(int i=1;i<=n;i++) {
		// 对于数组a中的每一个数字,分解质因数,计算在这n个数中的最大次数	
		for(int j=1;j<=idx;j++) {
			// 剪枝,如p[j]×p[j]>a[i],说明p[j]不可能为a[i]质因数
			if(p[j]*p[j]>a[i]) break;
			// 遍历质数数组
			int cnt=0; // 分解后p[i]的次数
			while(a[i]%p[j]==0) {
				cnt++;
				a[i]/=p[j];
			}
			m_max[p[j]]=max(m_max[p[j]],cnt); // 更新质因数p[i]出现的最大次数
		}
		// 本身是质数
		if(a[i]>1) {
			m_max[a[i]]=1; // 次幂只能为1
		}
	}
}

int main() {
	cin>>n;
	for(int i=1;i<=n;i++) {
		cin>>a[i];	
	}
	get_primes(1000);
	get_facts(a);
	// 打印测试
	int res=1;
	for(auto it=m_max.begin();it!=m_max.end();it++) {
		cout<<it->first<<' '<<it->second<<endl;
		for(int i=1;i<=it->second;i++) {
			res*=(it->first);
		}
	}
	cout<<res<<endl; // 公共LCM
	return 0;
}

/*
输入样例:
6
12 24 30 32 36 42
输出样例:
10080
 */
打赏
  • 版权声明： 本博客所有文章除特别声明外，著作权归作者所有。转载请注明出处！
  • Copyrights © 2015-2024 John Doe
  • 访问人数: | 浏览次数:

请我喝杯咖啡吧~

支付宝
微信