数论第一节

2023-08-06 17:39 由 MoiLip 发表于 #其他

数论

质数

在大于1的整数中，只包含1和本身这两个约数，就被称为质数，也叫素数
质数的判定
- 试除法
  - 遍历2-n，若有约数则不为质数 O(n)
  - 优化：
    - d整除n，则n/d也整除n，约数总是成对出现，只要找较小的约数，即取d <= n/d，则d <= sqrt(n) 只用遍历2-sqrt(n) O(sqrt(n))
    - 不用 i * i <= n ，i过大会溢出
    - sqrt()函数较慢，只用遍历 d--n/d，即限制范围为 i--n/i
  - 代码：
```
//不用for(int i = 1; i * i <= n; ++ i) i * i 会溢出
//不用for(int i = 1; i <= sqrt(n); ++ i) sqrt() 函数缓慢
//用for(int i = 1; i <= n / i; ++ i)  不会溢出，快
bool is_prime(int x){
	if(x < 2) return false;
	for(int i = 2; i <= n / i; ++ i)
		if(n % i == 0) return false;
	return true;
}
```

分解质因数

试除法

遍历2-n，找因子
n最多有一个大于sqrt(n)的因子，因此只用在2-sqrt(n)中找因子，最后判断最后一个因子是否为大于sqrt(n)的因子

代码：

//暴力做法
void divide(int n){
	for(int i = 2; i <= n; ++ i){
		if(n % i == 0){
			int s = 0; //i的个数
			while(n % i == 0){
				n /= i; //除干净
				s ++ ;
			}
			cout << i << s << endl;
		}
	}
}
//优化
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 ++ ;
			}
			cout << i << s << endl;
		}
	}
	if(n > 2) cout << n << 1;//n就是最后大于sqrt(n)的因子
}

筛选质数

埃氏筛法

从2-n，将每个数的倍数删掉，那么剩下的数就是质数 O(nln(n))
优化：
- 任何一个合数都可以拆成若干素数之积，因此只用将素数的倍数删掉 O(nln(ln(n))) ~ O(n)

代码：

int primes[N];
int st[N];//标记是否被筛过
void get_primes(int n){
	int cnt = 0;
	for(int i = 2; i <= n; ++ i){
		if(!st[i]){ //没有被筛过，说明是质数
			primes[ ++ cnt] = i;
			//筛该质数的所有倍数
			for(int j = i + i; j <= n; j += i) st[j] = 1;
		}
	}
}

线性筛法

数据大小在10^{7左右线性筛法比埃氏筛法快一倍，10}6左右差不多
n只会被它的最的最小质因子筛掉，利用最小质因子筛掉合数

代码：

int primes[N];
int st[N];
void get_primes(int n){
	int cnt = 0;
	for(int i = 2; i <= n; ++ i){
		if(!st[i]) primes[ ++ cnt] = i;//没有被筛掉就是质数
		for(int j = 1; primes[j] <= n / i; ++ j){//从小到大遍历质数
			st[primes[j] * i] = 1; //筛掉合数，若x是合数，当i遍历到x时，一定会先遍历到x的最小质因子prime，所以此时prime进入primes数组，当i遍历到x/prime时，x = prime*i会被筛掉，所以每个合数都能被筛掉，并且是在遍历到该合数之前被筛掉
			if(i % pimes[j] == 0) break; //i是合数筛掉i，i在之前就被标记过，所以不用再标记
		} 
	}
}

约数

求所有约数

试除法

代码：

vector<int> get_divisors(int n){
	vector<int> res;
	for(int i = 1; i <= n / i; ++ i){
		if(n % i == 0){
			res.push_back(i);
			if(i != n / i) res.push_back(n / i);
		}
	}
	sort(res.begin(), res.end());
	return res;
}

约数的个数

若\(N = p_1^{a_1} · p_2^{a_2} · p_3^{a_3} ··· ·p_n^{a_n}\) 其中p为N的所有质因子

则N的约数个数为：\((a_1+1)(a_2+1)(a_3+1)···(a_n+1)\)

代码：

const int mod = 1e7 + 10;
unordered_map<int, int> primes;//hash表存储每个质数有多少
void get_primes(int n){
	for(int i = 2; i <= n / i; ++ i){
		while(n % i == 0){
			n /= i;
			primes[i] ++ ;
		}
	}
	if(n > 1) primes[n] ++ ;
}
for(int i = 1; i <= n; ++ i) get_primes(a[i]);
long long res = 0;
for(auto p : primes) res = res * (p.second + 1) % mod;

则N的约数总和为：\((p_1^{0}+p_1^{2}+···+p_1^{n})(p_2^{0}+p_2^{1}+···+p_2^{n})···(p_n^{0}+p_n^{1}+···+p_n^{n})\)

代码：

const int mod = 1e7 + 10;
unordered_map<int, int> primes;
void get_primes(int n){
		for(int i = 2; i <= n / i; ++ i){
			while(n % i == 0){
				n /= i;
				primes[i] ++ ;
			}
		}
		if(n > 1) primes[n] ++ ;
	}
	for(int i = 1; i <= n; ++ i) get_primes(a[i]);
	long long res = 1;
	for(auto p : primes){
		long long t = 1;
		int a = p.first, b = p.second;
		while(b -- ) t = (t * a + 1) % mod;
		res = res * t % mod;
	}

最大公约数
- 辗转相除法（欧几里得算法）O(logn)
- a|b, a|c, 则 a|(b+c), 则a|(bx + cy)
- 求a与b的最大公约数，设其公约数为c，则c|a, c|b, c|(ax + by), 设a = kb + m, 则m = a - kb, 则c|m, 又m = a % b, 则 c|(a % b), 即a与b的最大公约数，也是a%b的公约数，即gcd(a, b) = gcd(b, a % b)
- 代码：
```
int gcd(int a, int b){
	return b ? gcd(b, a % b) : a;
}
```

数论

质数

质数的判定

试除法

分解质因数

试除法

筛选质数

埃氏筛法

线性筛法

约数

求所有约数

试除法

约数的个数

最大公约数