学习笔记——数论

写在前面...
通过写数论的md笔记，新知识不确定有没有学懂，但是我的md数学公式方法得到了极大的提升orz

质数的定义：

针对从2开始的整数定义，如果只包含1和本身这两个因数，则称该数为质数（素数）

（1）质数的判定：试除法

枚举因数的时候，只枚举到因数比较小的那个范围（根号n）

（2）分解质因数：试除法

从小到大枚举所有的数，对于质因子，可通过循环求出每个质因子的个数，从小往大除可以保证其因子一定是质数。

且\(n\)中最多只包含一个大于\(sqrt(n)\)的质因子

朴素筛法时间复杂度为\(O(nlogn)\)

1. 埃式筛法

定义及其原理：

每个合数都可以表示为多个质数的积，因此从最小的质数2开始，用每一个已找到的质数去筛选比它大的数，从而筛掉合数，剩下的就是素数。

算法过程：

1）从最小的质数2开始，遍历\(n\)以内的所有数\(i\)

2）对于当前数\(i\), 判断其是否是质数，如果是，则用\(i\)筛掉其在范围内的所有倍数，如\(i=3\)时，筛掉\(n\)以内的所有\(3\)的倍数。

3）不断重复过程2，直到遍历到\(n\)

时间复杂度\(O(nloglogn)\)

2. 线性筛法

原理：n只会被最小质因子筛掉，且合数一定会被筛掉

1） \(i\) % \(prime[j] == 0\)时：

\(prime[j]\)一定是\(i\)的最小质因子，且\(prime[j]\)一定是\(prime[j]*i\)的最小质因子

2） \(i\) % \(prime[j] != 0\)时：

\(prime[j]\)一定小于\(i\)的所有质因子，且\(prime[j]\)也一定是\(prime[j]*i\)的最小质因子

const int N = 10000010;
int primes[N], cnt;
bool st[N];

void get_primes(int n){
   for(int i = 2; i <= n; i++){
   	if(!st[i])	primes[cnt ++] = i;
   	//j从小到大枚举所有质数
   	for(int j = 0; primes[j] <= n / i; j++){
   		st[primes[j] * i] = true;
   		//当该条件成立的时候， prime[j]一定是i的最小质因子
   		if(i % primes[j] == 0)	break;
   	}
   }
}

质数定理

\(1～n\)中，有\(n/logn\)个质数

3. 约数

1）试除法求一个数的所有约数

从小到大枚举所有可能的数字，时间复杂度为\(O(logn)\)

2） 求约数个数

当\(N = p_1^{\alpha_1}* p_2^{\alpha_2}*...*p_k^{\alpha_k}\)

对于一个数的所有约数，一定可以由上面的通式来表示，且有所对应的\(\alpha_1\)、\(\alpha_2\)、\(\alpha_3\)。

约数用M表示，那么\(M = p_1^{\beta_1}* p_2^{\beta_2}*...*p_k^{\beta_k}\)

对于\(\beta_1\)、\(\beta_2\)、\(\beta_3\)的取值范围，为\(0~\)~\(\alpha_i\)，就能够表示出来所有的约数。所以求约数个数实际可拆解为组合数学（乘法原理）。

所以对于N而言，其对应的约数个数为\((\alpha_1+1)*(\alpha_2+1)*(\alpha_3+1)...(\alpha_k+1)\)

计算时间复杂度

对于i而言，n以内所有倍数的个数表示为\(n/i\)

所以n以内所有数的倍数个数表示为\(\sum_{i=1}^{i=n}{n/i}\)

3）求约数之和（没懂）

根据乘法原理和加法原理，约数之和可以表示为:

\(({p_1}^0+{p_1}^1+...+{p_1}^{\alpha_1})*({p_2}^0+{p_2}^1+...+{p_2}^{\alpha_2})*...*({p_k}^0+{p_k}^1+...+{p_k}^{\alpha_k})\)

4）欧几里得算法（辗转相除法）

求两数的最大公约数

通过原理：如果a能整除d，且b能整除d，那么ax+by也能够整除d，可推：

\(gcd(a,b)=gcd(b,a-c*b)\)

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

4. 欧拉函数

\(\phi(n)\)表示为1到\(n\)中和n互质的数的个数

\(p_1\)、\(p_2...\)\(p_n\)表示n的所有质因子

若\(n={p_1}^{\alpha_1}*{p_2}^{\alpha_2}*...*{p_k}^{\alpha_k}\)

那么\(\phi(n)=n*（1-\frac{1}{p_1}）*（1-\frac{1}{p_2}）*...*（1-\frac{1}{p_k}）\)

其时间复杂度为\(O(\sqrt{n})\)

该公式的证明需要用到容斥原理

方法:

从1～n中删掉所有\(p_1\)、\(p_2...\)\(p_n\)的倍数，那么剩下的数的个数就可以表示成\(n-\frac{p_1}{n}-\frac{p_2}{n}-...-\frac{p_k}{n}\)，但是这样会重复删除掉某些倍数

加上所有\(p_i*p_j\)的倍数的个数，因为这些数被删掉了两次，其个数可以表示为\(\frac{p_i*p_j}{n}\)

减去所有\(p_i*p_j*p_k\)的个数，其个数表示为\(\frac{p_i*p_j*p_k}{n}\)

一直重复上述过程，偶数因子数要加上，奇数因子数要减掉，直到覆盖掉所有的因子数。这个公式最后就可以由上面\(\phi(n)\)的式子表示

代码实现

int n;
cin >> n;
while(n--){
	int a;
	cin >> a;
	for(int i = 2; i <= a / i; i++){
		if(a % i == 0){
			res = res / i * (i - 1);
			while(a % i == 0)	a %= i;
		}
	}
	//最后如果还有剩 
	if(a > 1)	 res = res / a * (a - 1);
	cout << res << endl;
}

筛法计算欧拉函数

可以通过线性筛来算某一个数的所有质数，从而提高求欧拉函数的效率。

ll get_eulers(int n){
	phi[1] = 1;
	for(int i = 2; i <= n; i++){
		//如果i到当前还没有被筛掉的话，则证明i是一个质数
		if(!st[i]){
			primes[cnt ++] = i;
			//1～i-1以内与质数i互质的个数有
			phi[i] = i - 1;
		}
		//把所有i的倍数都筛掉
		for(int j = 0; primes[j] <= n / i; j++){
			st[primes[j] * i] = 1;
			if(i % primes[j] == 0){
				//公式推导，求i*prime[j]的质因子个数
				phi[i * primes[j]] = phi[i] * primes[j];
				break;
			}
			phi[i * primes[j]] = phi[i] * (primes[j] - 1);
		}
	}
	ll res = 0;
	for(int i = 1; i <= n; i++)		res += phi[i];
	return res;
}

欧拉定理

如果\(a\)和\(n\)互质，那么\(a^{\phi(n)}\equiv1(mod\quad n)\)

费马小定理

如果\(n\)是一个质数，且\(a\)和\(n\)互质，那么\(a^{n-1}\equiv1(mod\quad n)\)

5. 快速幂

快速幂：快速求解\(a\)的\(k\)次方模\(p\)的结果，其时间复杂度为\(O(logk)\)

其核心思路是预处理出来\(a^{2^0}\)\(a^{2^2}\)...\(a^{2^k}\)的模p下的值

\(a^k\) = \(a^{2^i}\) * \(a^{2^j}\) * \(a^{2^k}\)... = \(a^{2^i+2^j+2^k+...}\)

该式子即把k以二进制的形式表示。

int quick_mi(int a, int k, int p){
	int res = 1;
	while(k){
		if(k & 1)	res = (ll)res * a % p;
		k >>= 1;
		a = (ll)a * a % p;
	}
	return res;
}

快速幂求逆元

逆元：如果\(a\)能够整除\(b\)，希望找到一个数，实现\(\frac{a}{b}\equiv a*x(mod\quad p)\)

这个数\(x\)即叫做\(b\)模\(p\)的逆元，记做\(b^{-1}\)，所以\(\frac{a}{b}\equiv a*b^{-1}(mod\quad p)\)

左右两边把\(a\)删掉，同乘一个\(b\)，也就是\(b*b^{-1}\equiv1(mod\quad p)\)

由费马小定理可得到，如果\(p\)是质数，且\(b\)和\(p\)互质，那么\(b^{p-1}\equiv1(mod\quad p)\)，得到\(b*b^{p-2}\equiv1(mod\quad p)\)

对比逆元的公式，如果b是质数，那么b的逆元即等于\(b^{p-2}\)，即可以利用快速幂求解\(b^{p-2}\)

int res = quick_mi(a, p-2, p);
//如果a和p互质，那么a的p-2次方即为逆元
if(a % p ！= 0)		printf("%d\n", res);
//如果p是a的因子，那么对于a而言，不存在逆元
else		print("impossible");

6. 扩展欧几里得算法

裴蜀定理

对于任意一对正整数\(a\)和\(b\)，一定存在非零整数\(x\)和\(y\)，使得\(ax + by=gcd(a, b)\)

利用扩展欧几里得算法来求其系数\(x\)和\(y\)

int exgcd(int a, int b, int &x, int &y){    
	//b==0时找到结果
	if(!b){
		x = 1, y = 0;
		return a;
	}
	int d = exgcd(b, a % b, y, x);
	//公式推导
	y -= a / b * x;
    return d;
}

int main(){
	int a, b, x, y;
	scanf("%d %d %d %d", &a, &b, &x, &y);
	exgcd(a, b, x, y);
}

公式推导

边界条件：

当\(b==0\)时，\(gcd(a, 0)=a\)

又因为\(ax + by=gcd(a, b)\)

所以\(ax+by=a\)，\(x=1\)，\(y=0\)

递归情况：

\(ax + by=gcd(a, b)=gcd(b, a\) \(mod\) \(b)\)

交换x、y，把\(a\)用\(b\)代替，b用 \(a\) mod \(b\) 代替，\(d\)为\(gcd(a,b)\)，那么

\(by+(a\) \(mod\) \(b)x=d\)

\(by+(a-\lfloor{\frac{a}{b}}\rfloor b)x=d\)

\(ax+(y-\lfloor{\frac{a}{b}}\rfloor x)b=d\)

所以递归后的系数，\(x\)保持不变，\(y\)变成\(y-\lfloor{\frac{a}{b}}\rfloor x\)