基础数论 质数与约数

基础数论

前置芝士：

等比数列求和: \(S_n=a_0\frac{1-q^n}{1-q}\)

质数与约数：

整除与约数

设 \(n\) 为非负整数，\(d\) 为正整数，若 \(\frac{n}{d}\) 为整数，则称 \(d\) 整除 \(n\)，记为\(d\mid n\)。此时，则称 \(d\) 是 \(n\) 的约数，或因数、因子；称 \(n\) 为 \(d\) 的倍数。

质数与合数的定义：

对于 \(n \geq 2\) ，若 \(\forall 1<i<n,i\nmid n\) ，则称 \(n\) 为质数，否则 \(n\)​ 为合数。

质数判定：

试除法：

单次时间复杂度 \(O(\sqrt n\ )\)

bool is_prime(int n) {
	if(n < 2)
		return false;
	for(int i=2; i<= sqrt(n); ++i) {
		if(n % i == 0)
			return false;
	}
	return true;
}

质数筛法一：

从 \(2\) 到 \(n\) 枚举整数 \(i\)，标记大于 \(i\) 且不大于 \(n\) 的 \(i\) 的倍数。枚举到 \(i\) 时，若 \(i\) 没有被标记过，则 \(i\) 为质数。

时间复杂度 \(O(\sum_{i=1}^n \frac{n}{i})=O(n\log n)\)

void found_prime() {
	memset(vis, 0, sizeof(vis));
	vis[0] = 1; vis[1] = 1; // 特殊处理 0 和 1
	for(int i=2; i<=n; ++i) {
		for(int j=i*2; j<=n; j+=i)
			vis[j] = 1; // 标记合数
    }
}

埃氏筛：

只需要枚举质数的倍数就可以标记到所有合数了。实际上对于每个质数 \(p\) 而言，小于\(p^2\) 的 \(p\) 的倍数在扫描到更小的质数时就已经被标记过了。

从 \(2\) 到 \(n\) 枚举整数 \(i\)，若 \(i\) 是质数，则把 \(i^2\) , \((i+1) \times i\), \(\cdots\), \(\lfloor \frac{n}{i}\rfloor \times i\) 标记为合数。枚举到 \(i\) 时，若 \(i\) 没有被标记过，则 \(i\) 为质数。

时间复杂度 \(O(\sum_{pr[i]\leq n}\frac{n}{pr[i]})=O(n\log\log n)\)

void found_prime() {
	memset(vis, 0, sizeof(vis));
	vis[0] = 1; vis[1] = 1; // 特殊处理 0 和 1
	for(int i=2; i<=n; ++i) {
		if(!vis[i]) { // i 为质数
			for(int j=i*i; j<=n; j+=i)
				vis[j] = 1; // 标记合数
		}
	}
}

线性筛：

用每一个合数的最小质因子来标记这个合数。时间复杂度 \(O(n)\)

int pr[N],cnt;
bool vis[N];
void init(){
	int n=1e5+50;
	for(int i=2;i<=n;i++){
		if(!vis[i]){pr[++cnt]=i;}
		for(int j=1;j<=cnt&&i*pr[j]<=n;j++){
			vis[i*pr[j]]=1;
			if(i%pr[j]==0)break;
		} 
	}
}

区间筛：(埃氏筛)

const int maxn = 1e6+10;
typedef long long LL;
bool is_prime[maxn];  //标记a~b范围内的质数 
bool is_prime_small[maxn];  //标记 1~sqrt(n)范围内的所有质数 
LL a, b;

//对区间[a, b]内的整数执行筛法，is_prime[i-a]=true表示i是素数 
void found_prime()
{
	for(LL i=0; i*i<=b; ++i)
		is_prime_small[i] = true; 
	is_prime_small[1] = false;
	for(LL i=0; i<=b-a; ++i)
		is_prime[i] = true;
		
	for(LL i=2; i*i<=b; ++i) {
		if(is_prime_small[i]) {  // i是质数 
			for(LL j=i*i; j*j<=b; j+=i)  // 标记 sqrt(b) 以内的i的倍数 
				is_prime_small[j] = false;
			for(LL j = max(2LL, (a+i-1)/i) * i; j<=b; j+=i)  //标记[a, b]中i的倍数 
				is_prime[j-a] = false;
		}
	}	
}

算术基本定理:

任何一个大于 1 的正整数都能唯一分解为若干个质数的乘积。

设 \(n\geq2\) 为整数，有唯一的分解式：

其中 \(c_i\) 都是正整数，\(p_i\) 都是质数，且满足 \(p_1\leq p_2\leq...\leq p_m\)

根据算术基本的定理，对于任意一个大于 \(2\) 的整数 \(n\)，他的正约数集合可以写作：

推论一： \(n\) 的正约数个数为：

推论二： \(n\) 的所有正约数之和为：

阶乘分解：

对于一个数 \(n\) 求 \(n!\) 的质因数分解：

考虑对于一个质数 \(p_i\) 求 \(n!\) 中包含多少个 \(p_i\)
答案是 \(\sum_{i=1}^{\lfloor\log_pn\rfloor}\lfloor\frac{n}{p^i}\rfloor\)
对于每一个质数都用如上方式
共有 \(\frac{n}{\ln n}\) 个数，每次处理 \(\log n\) 的复杂度，总复杂度 \(O(n)\) 。

求解正约数集合：

试除法 求 \(n\) 的正约数：

时间复杂度 \(O(\sqrt n )\)

int divisor[10010], cnt = 0;
for(int i=1; i<=sqrt(n); ++i) {
	if(n % i == 0) {
		divisor[++cnt] = i;
		if(i != n/i) divisor[++cnt] = n/i;
	}
}

推论：一个整数 \(n\)的正约数个数最多不超过 \(2\times \sqrt n\) 个

倍数法 求\(1\sim n\)的正约数：

先枚举 \(1 \sim n\) 中的每一个数作为约数 \(d\)，再在 \(1\sim n\) 寻找 \(d\) 的倍数即可。时间复杂度 \(O(n+\frac{n}{2}+\cdots+\frac{n}{n})=O(n\log n)\)

vecotr<int> divisor[500010];
for(int i=1; i<=n; ++i) { // 先枚举约数 i
	for(int j=1; j<=n/i; ++j) //枚举 i 在 1~n 范围内的倍数 i × j
		divisor[i*j].push_back(i); // i 是 i × j 的约数
}

推论：\(1\sim n\) 的约数个数总和大约为 \(n\log n\) 个。

约数研究：

设 \(f(x)\) 为 \(x\) 的约数个数，求 \(\sum_{i=1}^nf(i)\)

可以枚举每一个 \(i\in[1,n]\) ，\(1\sim n\) 中含有 \(\lfloor\frac{n}{i}\rfloor\) 个约数 \(i\) 。所以答案为 \(\sum_{i=1}^n\lfloor\frac{n}{i}\rfloor\)

\({\rm gcd}\) :

\(\forall a,b\in \mathbb{N},d\in \mathbb{N^{*}}\) 若 \(d\mid a\ \&\ d\mid b\) 则称 \(d\) 为 \(a,b\) 的公约数。

\(a,b\) 的公约数中最大的称为 \(a,b\) 的最大公约数，记为 \(\gcd(a,b)\)。

性质:

• \(\gcd(a,b)=\gcd(b,a)\)
• 对于 $\forall a,b\in \mathbb{N} $ 若 \({\rm gcd}(a,b)=1\) 则称 \(a,b\) 互质。
• 由于任何正整数都是 \(0\) 和 \(0\) 的公约数，故 \(\gcd (0,0)\) 不存在。
• 对于 \(\forall a\in \mathbb{N^{*}}\) ，有 \(\gcd(a,a)=a,\gcd(a,0)=a\) 。
• \(\forall k\in \mathbb{Z}\)，有 \(\gcd(k\times a,k\times b)=k\times \gcd(a,b)\) 。

更相减损术：

\(\forall a,b\in \mathbb{N^{*}}\ \&\ a\geq b\) 有 \(\gcd(a,b)=\gcd(b,a-b)=\gcd(a,a-b)\)

\(\forall d\mid a\ \&\ d\mid b\)，有 \(a=k_1\times d,b=k_2\times d\) ，则 \((a-b)=(k_1-k_2)\times d\) ，所以 \(d\) 也是 \(b,a-b\) 的公约数，所以 \(\gcd(a,b)=\gcd(b,a-b)\)​ 。

辗转相除法：

\(\forall a,b\in \mathbb{N^{*}}\ \&\ b!=0\) 有 \(\gcd(a,b)=\gcd(b,a\bmod b)\)

• 若 \(a<b\) ，则 \(\gcd(b,a\bmod b)=gcd(b,a)=gcd(a,b)\)
• 若 \(a\geq b\) ，设 \(a=q\times b+r\) ，其中 \(0\leq r <b\) 。\(r=a\bmod b\) 。有 \(a=k_1\times d,q\times b=k_2\times d\) ，则 \(r=(a-q\times b)=(k_1-k_2)\times d\) ，因此 \(d\) ，也是 \(b,r\) 的公约数，故 \(\gcd(a,b)=\gcd(b,a\bmod b)\)

代码：

int gcd(int a, int b) {
	while(b > 0 ) {
		int x = a % b;
		a = b;
		b = x;
	}
	return a;
}

递归：

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

最大复杂度 \(O(\log(a+b))\)

\({\rm lcm}\)：

\(\forall a,b\in\mathbb{N^{*}},m\in \mathbb{N}\) 若 \(a\mid m\ \&\ b\mid m\)，则称 \(m\) 为 \(a\) 和 \(b\) 的公倍数。

\(a,b\) 的公倍数中最小的称为 \(a,b\) 的最小公倍数，记为 \({\rm lcm}(a,b)\) 。

实际代码中： \({\rm lcm(a,b)=\frac{a}{\gcd(a,b)}\times b}\)

gcd与lcm：

给出某两个整数 \(a\) 和 \(b\) （\(a\leq b\)）的最大公约数 \(GCD\) 和最小公倍数 \(LCM\) ，请找出满足的 \(a\) 和 \(b\) ，使得 \(b-a\) 的值最小。

\(\because LCM=\frac{a\times b}{GCD}\)
\(\therefore \frac{a\times b}{GCD^2}=\frac{LCM}{GCD} \Rightarrow (\frac{a}{GCD})^2\leq \frac{LCM}{GCD}\)
\(\therefore \frac{a}{GCD}\leq \sqrt{\frac{LCM}{GCD}}\)
设 \(a'=\frac{a}{GCD}\) ，从 \(\sqrt{\frac{LCM}{GCD}}\sim 1\) 来枚举 \(a'\) ，当 \(a'\mid \frac{LCM}{GCD}\&\& \gcd(a',LCM/GCD/a')=1\) 时停止枚举。
答案即为 \(a=a'\times GCD,b=\frac{LCM}{a'}\)

CF1152C：

给定两个正整数 \(a,b\) ，找到非负整数 \(k\) 使 \(a+k\) 与 \(b+k\) 的最小公倍数最小，如有多解输出最小的 \(k\) 。

设 \(a>b\) 显然 \({\rm lcm}(a+k,b+k)=\frac{(a+k)(b+k)}{\gcd(a+k,b+k)}\)
由辗转相除法可知 \(\gcd(a,b)=\gcd(b,a-b)\)
所以 \({\rm lcm}(a+k,b+k)=\frac{(a+k)(b+k)}{\gcd(b+k,a-b)}\)
所以可以枚举 \(a-b\) 的因子 \(w\) ，若 \(b\%w=0\) 则 \(k=0\) ，否则 \(k=(\lfloor\frac{b}{w}\rfloor+1)w-b\)
by ysx