素性测试

素性测试就是判断某个数是否为质数。

费马小定理

内容：若 \(p\) 为质数，\(a\)为任意整数，有 \(a^{p-1}\equiv 1(mod\ p)\)

那么可以多次随机取一个基数 \(a\in (1,p)\) 若 \(p\) 满足上式，那么它为质数的可能性就越大。

Millar Rabin 素性测试

inline ll qpow(ll a, ll n, ll mod){
	ll ans = 1;
	while(n){
		if(n & 1) ans = (__int128)a * ans % mod;
		a = (__int128)a * a % mod;
		n >>= 1;
	} return ans;
}
inline bool MillarRabin(ll n){
	if(n < 3 || n%2 == 0) return n == 2;
	ll u = n-1, t = 0;
	while(!(u%2)) u >>= 1, ++t;
	for(int i=1; i<=8; ++i){
		ll a = rand()%(n-2) + 2, v = qpow(a, u, n), s;
		if(v == 1) continue;
		for(s=0; s<t; ++s){
			if(v == n-1) break;
			v = qpow(v, 2, n);
		}
		if(s == t) return false;
	} return true;
}

唯一分解定理

任何一个大于1的整数n都可以分解成若干个素因数的连乘积。\(n=p_1^{k1}p_2^{k2}p_3^{k3}p_4^{k4}...\)

这条定理看似简单实则非常厉害，可以吧许多复杂的数论问题转化到质因子层面上。

约数和定理

任意一个大于1的整数 \(n\) 的因数和都可以表示为 \(\sum {ki+1}\)。证明很简单，对所有质因子的系数排列组合+乘法原理即可。

分解质因数

试除法

看道例题 阶乘分解。

不难发现：\(n!\) 的质因数即为从1到n所有的质数，可以使用欧拉筛，但问题在于如何求质因数的系数。通过找规律(找了我一个多小时