数论笔记

♠ use C++11

倍数

1. 若 (a,b,k in mathbb N)，且 (a imes k=b)，那么 (b) 是 (a) 的倍数，称 (a) 整除 (b)，记作 (a mid b)。

2. ([1,n]) 中 (x in mathbb N) 的倍数有 (left lfloor dfrac{n}{x} ight floor) 个。

约数

1. 若 (a mid b)，那么 (a) 是 (b) 的约数。

2. (a in mathbb N) 的约数个数是有限的，记作 (operatorname d(n))。

3. 快速算一个序列的 (operatorname d(n))：设一个计数数组对应每个数，初始为 0，从左到右计算每个数，对于每个倍数加 1，当整个序列计算完后，计数数组的值是其对应数字的约数个数，时间复杂度 (mathcal{O}(noperatorname{log}n))。下面是一个例子：

n    1 2 3 4 5 6
d(n) 0 0 0 0 0 0 start
     1 1 1 1 1 1 step 1 in number 1
     1 2 1 2 1 2 step 2 in number 2
     1 2 2 2 1 3 step 3 in number 3
     .....more

素数

1. 1 不是素数也不是合数。

2. 下面是一串判断 (nin mathbb N) 是否是素数的代码，时间复杂度 (mathcal{O}(sqrt n))。

bool is_prime(long long n){
	if(n==1)	return false;
	for(long long i=1;i<=n/i;++i){
		if(x%i==0)	return false;
	}
	return true;
}

3. 计算一个序列每个数是否是素数：朴素筛法，有较多重复判断，时间复杂度 (mathcal{O}(noperatorname{log}n))；埃式筛法，仅是素数才向后筛，优化朴素筛法，时间复杂度 (mathcal{O}(noperatorname{log log}n))，接近线性筛。

最大公约数

1. 若 (a,bin mathbb N) 且 (k mid a,b)，且不存在更大的 (k)，称 (k) 是 (a,b) 的最大公约数。

2. 快速求 (a,bin mathbb N) 的最大公约数，欧几里得定理：(gcd(a,b)=gcd(b,a mod b))。

3. 已知 (a,b in mathbb N)，可找到 (x,y in mathbb Z) 使 (ax +by=gcd(a,b))，若 (ax+by=1) 有解，则 (a) 和 (b) 互质。

4. 扩展欧几里得，一定存在 (x,yin mathbb Z) 使贝祖等式 (ax +by=gcd(a,b))(Rightarrow (left lfloor a div b ight floor imes b + a mod b) x + b imes y = gcd(b,amod b))(Rightarrow (left lfloor a div b ight floor imes x + y) b +(a mod b) imes x)，可得新的方程 (b imes x”+(a mod b) imes y” = gcd(b,amod b)) 因此可得 (egin{cases}x”=(left lfloor a div b ight floor imes x+y)\y”=xend{cases})，同样倒推可得特解 (egin{cases}x=y”\y=x”-(left lfloor a div b ight floor imes y”)end{cases})，下面是递归代码实现：

array<int,3> exgcd(int a,int b){
	if(b==0){
		return {1,0,a};
		//当b=0时，等式为ax=gcd(a,0)，即ax=a
		//得x=1,y=0
	}
	array<int,3> ans=exgcd(b,a%b);
	int temp=ans[0];
	ans[0]=ans[1];
	ans[1]=temp-a/b*ans[1];
	return ans;//ans[0]为x，ans[1]为y，ans[2]为gcd(a,b)
}

5. 当求得贝祖等式特解 (x_0,y_0in mathbb Z) 后，可得 (x,yin mathbb Z) 通解，设 (g=gcd(a,b)) 通解为 (egin{cases}x=x_0+bdiv g imes t\y = y_0+a div g imes tend{cases})，推导过程：(egin{cases}ax+by=g\ax_0+bx_0=gend{cases})(Rightarrow (x-x_0)a+(y-y_0)b=0)(Rightarrow (x-x_0)a=(y_0-y)b)(Rightarrow Rightarrow (x-x_0)dfrac{a}{g}=(y_0-y)dfrac{b}{g})