数论 1

1. 质数

定义就不说了吧。

性质 & 定理

• 质数 p 有且仅有两个质因子 1 和 p 。

• 质数有无穷个。

• [1,n] 中的质数个数约为 nln⁡n (此结论可用来大致估算某些数论题的数据范围)。

• 任何一个大于 1 的整数 N 都可以分解成 N=∏i=1kpiαi(∀i,pi∈P,ai∈N∗) 的形式，如果不计各个质因数的顺序，那么这种分解是惟一的。

筛质数——线性筛法

线性筛法，顾名思义，可以筛出 [1,n] 内的所有质数，时间复杂度为 O(n) 。

int primes[N], cnt;
// primes存放所有的质数，cnt是质数的数量
int st[N];
// st[i]记录每个数是否是质数

void init(int n){
    for(int i = 2; i <= n; ++i){
        if(!st[i]) primes[cnt++] = i;
        for(int j = 0; primes[j] * i <= n && j < cnt; ++j){
            st[primes[j] * i] = 1;
            if(i % primes[j] == 0) break;
        }
    }
}

2. 约数

定义还是就不说了吧。~~

性质 & 定理

• 对于任何一个大于 1 的整数 N，如果将其分解质因数为 N=∏i=1kpiαi(∀i,pi∈P,ai∈N∗) 的形式，那么 N 的正约数个数为 ∏i=1k(αi+1) ， N 的所有正约数的和为 ∏i=1k(∑j=0αipij) 。
• 231 内约数个数最多的数有 1600 个约数；263 内约数个数最多的数有 138240 个约数。

求约数个数

对于要重复计算多次的，先筛出质数，代码效率会有所提高。

int get_divisors(int x){
	int res = 1, s;
	for(int i = 0; primes[i] < x / primes[i]; ++i){
		int p = primes[i];
		s = 0;
		while(x % p == 0){
			++s;
			x /= p;
		}
		res *= s + 1;
	}
	if(x > 1) res *= 2;
    // 这里一定记得判断是否有还没除尽的质因子
	
	return res;
}

3. 欧拉函数 φ

φ(n) 表示小于等于 n 的正整数中与 n 互质的数的个数。

对于任何一个大于 1 的整数 N，如果将其分解质因数为 N=∏i=1kpiαi(∀i,pi∈P,ai∈N∗) 的形式，那么：

特别地，φ(1)=1 。

性质 & 定理

有一堆，慢慢看吧，理性了解，证明的话有兴趣可以自己去搜索。

• 对于质数 p，φ(p)=p−1 。
• 若 p 为质数，n=pk(k∈N∗) ，那么 φ(n)=pk−pk−1 。
• 若 a∣n，那么 φ(an)=aφ(n) 。
• 若 (n,m)=1 ，那么 φ(n)φ(m)=φ(nm) 。
• 当 n>2 时，φ(n) 为偶数。
• 若 n 为大于 1 的正整数，那么在小于等于 n 的正整数中，与 n 互质的数之和为 nφ(n)2 。
• n=∑d∣n,φ(d) 。

4. 线性筛法求欧拉函数 φ

利用线性筛法以及欧拉函数的性质，可以筛出 [1,n] 内的所有质数，顺便求出 [1,n] 内的所有整数的欧拉函数，时间复杂度为 O(n) 。

int primes[N], cnt;
int phi[N];
bool st[N];

void init(int n){
    phi[1] = 1;
    for(int i = 2; i <= n; ++i){
        if(!st[i]){
            primes[cnt++] = i;
            phi[i] = i - 1;
            // 前面的性质1
        }
        for(int j = 0; primes[j] * i <= n && j < cnt; ++j){
            st[primes[j] * i] = 1;
            if(i % primes[j] == 0){
                phi[i * primes[j]] = phi[i] * primes[j];
                // 性质3
                break;
            }
            phi[i * primes[j]] = phi[i] * (primes[j] - 1);
            // 这个可以直接由计算方法推出来
        }
    }
}

5. 欧拉定理

Content

若 a,n∈N∗ ，且 (a,n)=1 ，则有：

aφ(n)≡1(modn)

特别地，当 n∈P 时，这就成了费马小定理

若 p∈P ，且 p∤a 则有：

ap−1≡1(modp)

6. 综合应用

Eg1

给定整数 N，将 N! 分解质因数，按照算术基本定理的形式输出分解结果中的 pi 和 ci 。

按照 pi由小到大的顺序输出。

• 3≤N≤106

首先 N≤106 ，所以 N! 会很大，直接分解肯定不行，考虑从 N! 的特殊性质入手。

N!=1×2×⋯×N

那么对于一个质数 p ，1∼N 中的 p,2p,…,kp （ p 的倍数）肯定含有质因子 p ，可以很容易得出个数为 ⌊Np⌋ 。

但这还会漏掉一些，如果一个数中含有 2 个因子 p ，会被漏算一次，因此还需要加上 1∼N 中的 p2,2p2,…,kp2 ，有 ⌊Np2⌋ 个。

以此类推，N! 中某个质因子 p 的次数为

那么接下来枚举所有小于等于 N 的质数，再分别求和就好了，时间复杂度 O(N) 左右吧（有点不好分析，反正过肯定是没问题的）。

Code

#include <cstdio>

using namespace std;
typedef long long ll;

const int N = 1e6 + 10;

int n;
int primes[N], cnt;
bool st[N];

void init(int n){
	for(int i = 2; i <= n; ++i){
		if(!st[i]) primes[cnt++] = i;
		for(int j = 0; primes[j] * i <= n && j < cnt; ++j){
			st[primes[j] * i] = 1;
			if(i % primes[j] == 0) break;
		}
	}
}

int main(){
	scanf("%d", &n);
	init(n);
	
	for(int i = 0; i < cnt; ++i){
		int p = primes[i], s = 0;
		int k = n;
		while(k){
			s += k / p;
			k /= p;
		}
		printf("%d %d\n", p, s);
	}
	
	return 0;
}

Eg2 洛谷P2158 [SDOI2008] 仪仗队

作为体育委员，C 君负责这次运动会仪仗队的训练。仪仗队是由学生组成的 n×n 的方阵，为了保证队伍在行进中整齐划一，C 君会跟在仪仗队的左后方，根据其视线所及的学生人数来判断队伍是否整齐（如下图）。

现在，C 君希望你告诉他队伍整齐时能看到的学生人数。

• 对于 100% 的数据，1≤n≤40000。

首先进行分析，将仪仗队放在一个平面直角坐标系中，无法看到的学生是因为被在同一条从原点出发的直线上的前面的学生挡住了。

那么可以得到学生能被看到的条件是横纵坐标互质。

答案就是：

最后加上的两个是 (0,1) 和 (1,0) 。

上式变一下（配合着图可能更好理解一些）：

这里我们惊喜的发现，可以用 φ(i) 来表示 ∑j=1i[gcd(i,j)=1]

于是，最后的柿子就出来咯：

当然，当 n=1 时，是没有学生的，也不满足上面的结论，需要特判一下。

代码就很好实现啦，用线性筛求个欧拉函数就可以 AC 此题，O(n) 根本不虚。

Code

#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;
typedef long long ll;

const int N = 40010;

int T, n, res = 1;	// +1跑到这里来了哦
int primes[N], cnt;
int phi[N];
bool st[N];

void init(int n){
	phi[1] = 1;
	for(int i = 2; i <= n; ++i){
		if(!st[i]){
			primes[cnt++] = i;
			phi[i] = i - 1;
		}
		for(int j = 0; primes[j] * i <= n && j < cnt; ++j){
			st[primes[j] * i] = 1;
			if(i % primes[j] == 0){
				phi[i * primes[j]] = phi[i] * primes[j];
				break;
			}
			phi[i * primes[j]] = phi[i] * (primes[j] - 1);
		}                          
	}
}

int main(){
	scanf("%d", &n);
	if(n == 1){
		puts("0");
		return 0;
	}
	init(n);
	
	for(int i = 1; i < n; ++i) res += 2 * phi[i];
	
	printf("%d\n", res);
	return 0;
}

---

蒟蒻很弱，如有错漏还请各位大佬指出

感谢~~~

__EOF__