【学习笔记】简单数论-质数-526互联

质数的个数是无限的。
- 试除法：若一个正整数 \(N\) 为合数，则存在一个能整除 \(N\) 的数 \(T\) ，其中 \(2 \le T \le \sqrt{N}\) 。
  - 时间复杂度为 \(O(\sqrt{N})\) 。
  - 代码实现
```
bool isprime(int n)
{
	if (n < 2)
		return false;
	for (int i = 2; i <= sqrt(n); i++)
		if (n % i == 0)
			return false;
	return true;
}
```
- 筛法
  - Eratosthenes 筛法（埃式筛法）
    - 时间复杂度 \(O(N \times \log \log N)\)
    - luogu P3912 素数个数
```
#include<bits/stdc++.h>
using namespace std;
bool m[100000010];
int main()
{
	int n,i,j,ans=0;
	cin>>n;
	m[1]=1;
	for(i=2;i<=sqrt(n);i++)
	{
		if(m[i]==0)
		{
			for(j=2;i*j<=n;j++)
			{
				m[i*j]=1;
			}

		}
	}
	for(i=2;i<=n;i++)
	{
		if(m[i]==0)
		{
			ans++;
		}
	}
	cout<<ans;
	return 0;
}
```
  - 线性筛法（欧拉筛法）
    - 时间复杂度 \(O(N)\)
    - luogu P3383 【模板】线性筛素数
```
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define sort stable_sort
#define endl '\n'
int prime[100000001],sum[10],len=0;
bool vis[100000001];
void isprime(int n)
{
	int i,j;
	memset(vis,false,sizeof(vis));
	for(i=2;i<=n;i++)
	{
		if(vis[i]==false)
		{
			len++;
			prime[len]=i;
		}
		for(j=1;j<=len&&i*prime[j]<=n;j++)
		{
			vis[i*prime[j]]=true;
			if(i%prime[j]==0)
			{
				break;
			}
		}
	}
}
int main()
{
	int n,q,i,k;
	cin>>n>>q;
	isprime(n);
	for(i=1;i<=q;i++)
	{
		cin>>k;
		cout<<prime[k]<<endl;
	}
	return 0;
}
```
- 算术基本定理（唯一分解定理）
  - 任何一个大于 \(1\) 的正整数都能唯一分解成有限个的质数的乘积，可写作 \(N=p_1^{c_1}p_2^{c_2}……p_m^{c_m}\) ，其中 \(c_i\) 都是正整数， \(p_i\) 都是质数，且满足 \(p_1<p_2<……<p_m\) 。
- 互质
  - 若 \(\forall a,b \in \mathbb{N},\gcd(a,b)=1\) ，则称 \(a,b\) 同余。
  - 对于三个数或更多个数的情况，将 \(\gcd(a,b,c)=1\) 的情况称为 \(a,b,c\) 互质；将 \(\gcd(a,b)=\gcd(a,c)=\gcd(b,c)=1\) 的情况称为 \(a,b,c\) 两两互质。
- 欧拉函数
  - \(1 \sim N\) 中与 \(N\) 互质的数的个数被称为欧拉函数，记作 \(\varphi(N)\) 。
  - 依据算术基本定理，有 \(N=p_1^{c_1}p_2^{c_2}……p_m^{c_m}\) ，则 \(\varphi(N)=N \times \dfrac{p_1-1}{p_1} \times \dfrac{p_2-1}{p_2} \times ... \times \dfrac{p_m-1}{p_m}=N \times \prod\limits_{i=1}^{m}{(1- \dfrac{1}{p_i})}\) ，其中 \(c_i\) 都是正整数， \(p_i\) 都是质数，且满足 \(p_1<p_2<……<p_m\) 。
    - 证明：设 \(p,q(p \ne q)\) 是 \(N\) 的质因子， \(1 \sim N\) 中 \(p\) 的倍数共有 \(\left\lfloor\dfrac{N}{p}\right\rfloor\) 个， \(q\) 的倍数共有 \(\left\lfloor\dfrac{N}{q}\right\rfloor\) 个，依据容斥原理， \(1 \sim N\) 中不与 \(N\) 含有共同质因子 \(p\) 或 \(q\) 的个数为 \(N -\left\lfloor\dfrac{N}{p}\right\rfloor-\left\lfloor\dfrac{N}{q}\right\rfloor+\left\lfloor\dfrac{N}{p \times q}\right\rfloor=\left\lfloor N \times (1- \dfrac{1}{p}- \dfrac{1}{q}+ \dfrac{1}{p \times q})\right\rfloor=\left\lfloor N \times (1- \dfrac{1}{p}) \times (1- \dfrac{1}{q})\right\rfloor\) 。类似地，可在 \(N\) 的全部质因子上使用容斥原理，即可得到与 \(N\) 互质的数的个数。
  - 性质
    - \(\varphi(1)=1\) 。
    - 若 \(p\) 为质数，则 \(\varphi(p)=p-1,\varphi(p^k)=p^k-p^{k-1}=(p-1) \times p^{k-1}\) 。
      - 证明：设 \(n=p^k\) ，比 \(n\) 小的正整数有 \(p^k-1\) 个。其中共有 \(p^{k-1}-1\) 个数能被 \(p\) 整除，即这些数不与 \(p^k\) 互质。故 \(\varphi(p^k)=p^k-1-(p^{k-1}-1)=p^k-p^{k-1}=(p-1) \times p^{k-1}\) 。
    - 对于两个不同的质数 \(p,q\) ，有 \(n=p\times q\) ，则 \(\varphi(n)=(p-1)(q-1)\) 。
    - 若 \(\forall n>1\) ，则 \(1 \sim n\) 中与 \(n\) 互质的数的和为 \(\dfrac{n \times \varphi(n)}{2}\) 。
      - 证明：依据更相减损法，有 \(\gcd(n,x)=\gcd(n,n-x)\) ，即与 \(n\) 互质的数 \(x,n-x\) 成对出现，平均值为 \(\dfrac{n}{2}\) 。
    - 若 \(n\) 为奇数，则 \(\varphi(2n)=\varphi(2) \times \varphi(n)=\varphi(n)\) 。
    - 若 \(2<n\) ，则 \(2|\varphi(n)\) 。
    - 若 \(a,b\) 互质，则 \(\varphi(ab)=\varphi(a) \times \varphi(b)\) 。
      - 证明：依据算术基本定理，设 \(a=\prod\limits_{i=1}^n p_i^{c_i},b=\prod\limits_{i=1}^m q_i^{c'_i}\) ，又因为 \(a,b\) 互质，所以不存在一组 \(i,j\) 满足 \(p_i=q_j\) ，故 \(\varphi(ab)=ab \times \prod\limits_{i=1}^n (1-\dfrac{1}{p_i}) \times \prod\limits_{i=1}^m (1-\dfrac{1}{q_i})\) ，又有 \(\varphi(a)=a \times \prod\limits_{i=1}^n (1-\dfrac{1}{p_i}),\varphi(b)=b \times \prod\limits_{i=1}^m (1-\dfrac{1}{1_i})\) ，故 \(\varphi(ab)=\varphi(a) \times \varphi(b)\) 。
      - 由本条性质可知 \(\varphi\) 是积性函数。
    - 若 \(a|b\) ，则 \(\varphi(ab)=a \times \varphi(b)\) 。
      - 证明：因为 \(ab\) 和 \(b\) 所有的质因子是相同的，只是部分质因子的指数发生变化，故 \(\varphi(ab)=a \times \varphi(b)\) 。
    - 若 \(a|b\) ，则 \(\varphi(a) | \varphi(b)\) 。
    - 若 \(p\) 为质数，且 \(p|n,p^2|n\) ，则 \(\varphi(n)=\varphi(\dfrac{n}{p}) \times p\) 。
      - 证明：因为 \(p|n,p^2|n\) ，所以 \(n,\dfrac{n}{p}\) 有相同的质因子（其中 \(p\) 的指数不同），依据欧拉函数的计算公式，此时有 \(\dfrac{\varphi(n)}{\varphi(\dfrac{n}{p})}=p\) ，故 \(\varphi(n)=\varphi(\dfrac{n}{p}) \times p\) 。
    - 若 \(p\) 为质数，且 \(p|n,p^2 \nmid n\) ，则 \(\varphi(n)=\varphi(\dfrac{n}{p}) \times (p-1)\) 。
      - 证明：因为 \(p|n,p^2|n\) ，所以 \(n,\dfrac{n}{p}\) 互质，又因为 \(\varphi\) 是积性函数，故 \(\varphi(n)=\varphi(\dfrac{n}{p}) \times \varphi(p)=\varphi(\dfrac{n}{p}) \times (p-1)\) 。
    - \(n=\sum\limits_{d|n}^{}\varphi(d)\) 。
      - 证明：设 \(k\) 满足 \(k<n,\gcd(k,n)=d\) ，则 \(\gcd(\dfrac{k}{d},\dfrac{n}{d})=1\) ；设 \(f(x)\) 表示满足 \(\gcd(k,n)=x\) 的 \(k\) 的个数，则 \(n=\sum\limits_{i=1}^n f(i)\) 。又因为 \(\dfrac{k}{x}\) 与 \(\dfrac{n}{x}\) 互质，有 \(f(x)=\varphi(\dfrac{n}{x})\) ，则 \(n=\sum\limits_{i|n}^{}\varphi(\dfrac{n}{i})\) 。易知 \(i\) 与 \(\dfrac{n}{i}\) 是一一对应的，故 \(n=\sum\limits_{d|n}^{}\varphi(d)\) 。
    - 依据算术基本定理，有 \(n=\prod\limits_{i=1}^m p_i^{c_i}\) ，又因为 \(\varphi\) 是积性函数，则 \(\varphi(n)=\prod\limits_{i=1}^m \varphi(p_i^{c_i})=\prod\limits_{i=1}^m (p_i-1) \times p_i^{{c_i}-1}=\prod\limits_{i=1}^m (1-\dfrac{1}{p_i}) \times p_i^{c_i}=n \times \prod\limits_{i=1}^m (1-\dfrac{1}{p_i})=n \times \prod\limits_{i=1}^m \dfrac{p_i-1}{p_i}\) 。
      - PS：无意义（用计算式证定义，又用定义证计算式）。
    - 若 \(n\) 为正整数，则 \(\sum\limits_{i=1}^{n} \gcd(i,n)=\sum\limits_{d|n}^{} d \times \varphi({\dfrac{n}{d}})\) 。
      - luogu P2303 [SDOI2012] Longge 的问题
      - 证明：
        
        \(\begin{aligned}\sum\limits_{i=1}^{n} \gcd(i,n) \end{aligned}\)
        
        \(\begin{aligned}&=\sum\limits_{d|n}^{} d \times \sum\limits_{i=1}^{n} [\gcd(i,n)=d] \end{aligned}\)
        
        \(\begin{aligned}&=\sum\limits_{d|n}^{} d \times \sum\limits_{i=1}^{\dfrac{n}{d}} [\gcd(i,\dfrac{n}{d})=1] \end{aligned}\)
        
        \(\begin{aligned}&=\sum\limits_{d|n}^{} d \times \varphi({\dfrac{n}{d}})\end{aligned}\)
    - 若 \(n\) 为正整数，则 \(\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} \gcd(i,j)=\sum\limits_{d=1}^{n} \varphi(d) \times \left\lfloor\dfrac{n}{d}\right\rfloor^2\) 。
      - luogu P2398 GCD SUM
      - 证明：
        
        \(\begin{aligned}\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} \gcd(i,j) \end{aligned}\)
        
        \(\begin{aligned}&=\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} \sum\limits_{d| \gcd(i,j)}^{} \varphi(d) \end{aligned}\)
        
        \(\begin{aligned}&=\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} \sum\limits_{d|i,d|j}^{} \varphi(d) \end{aligned}\)
        
        \(\begin{aligned}&=\sum\limits_{d=1}^{n} \varphi(d) \sum\limits_{i=1}^{n} [d|i] \sum\limits_{j=1}^{n} [d|j] \end{aligned}\)
        
        \(\begin{aligned}&=\sum\limits_{d=1}^{n} \varphi(d) \left\lfloor\dfrac{n}{d}\right\rfloor \left\lfloor\dfrac{n}{d}\right\rfloor \end{aligned}\)
        
        \(\begin{aligned}&=\sum\limits_{d=1}^{n} \varphi(d) \times \left\lfloor\dfrac{n}{d}\right\rfloor^2 \end{aligned}\)
      - 拓展：若 \(n,m\) 为正整数，则 \(\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{m} \gcd(i,j)=\sum\limits_{d=1}^{\min(n,m)} \varphi(d) \times \left\lfloor\dfrac{n}{d}\right\rfloor \times \left\lfloor\dfrac{m}{d}\right\rfloor\) 。
        
        证明：
        
        \(\begin{aligned}\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{m} \gcd(i,j) \end{aligned}\)
        
        \(\begin{aligned}&=\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{m} \sum\limits_{d| \gcd(i,j)}^{} \varphi(d) \end{aligned}\)
        
        \(\begin{aligned}&=\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{m} \sum\limits_{d|i,d|j}^{} \varphi(d) \end{aligned}\)
        
        \(\begin{aligned}&=\sum\limits_{d=1}^{\min(n,m)} \varphi(d) \sum\limits_{i=1}^{n} [d|i] \sum\limits_{j=1}^{m} [d|j] \end{aligned}\)
        
        \(\begin{aligned}&=\sum\limits_{d=1}^{\min(n,m)} \varphi(d) \left\lfloor\dfrac{n}{d}\right\rfloor \left\lfloor\dfrac{n}{d}\right\rfloor \end{aligned}\)
        
        \(\begin{aligned}&=\sum\limits_{d=1}^{\min(n,m)} \varphi(d) \times \left\lfloor\dfrac{n}{d}\right\rfloor \times \left\lfloor\dfrac{m}{d}\right\rfloor\end{aligned}\)
    - 若 \(n\) 为正整数，则 \(\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} \gcd(i,j)= \sum\limits_{d=1}^{n}d \times \;(\;2 \times \;(\;\sum\limits_{i=1}^{\dfrac{n}{d}}\varphi(i)\;)\;-1)\) 。
      - luogu P2398 GCD SUM
      - 证明：
        
        \(\begin{aligned}\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} \gcd(i,j) \end{aligned}\)
        
        \(\begin{aligned}&=\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} \sum\limits_{d=1}^{n}d \times [\gcd(i,j)=d] \end{aligned}\)
        
        \(\begin{aligned}&=\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} \sum\limits_{d=1}^{n}d \times [\gcd(\dfrac{i}{d},\dfrac{j}{d})=1] \end{aligned}\)
        
        \(\begin{aligned}&=\sum\limits_{d=1}^{n}d \times \sum\limits_{i=1}^{\dfrac{n}{d}} \sum\limits_{j=1}^{\dfrac{n}{d}} [\gcd(i,j)=1] \end{aligned}\)
        
        \(\begin{aligned}&=\sum\limits_{d=1}^{n}d \times \;(\sum\limits_{i=1}^{\dfrac{n}{d}} \times \;(2\;(\sum\limits_{j=1}^{i} [\gcd(i,j)=1])\;)\;-1) \end{aligned}\)
        
        \(\begin{aligned}&=\sum\limits_{d=1}^{n}d \times \;(\;(\;\sum\limits_{i=1}^{\dfrac{n}{d}} \times 2\varphi(i)\;)\;-1) \end{aligned}\)
        
        \(\begin{aligned}&=\sum\limits_{d=1}^{n}d \times \;(\;2 \times \;(\;\sum\limits_{i=1}^{\dfrac{n}{d}}\varphi(i)\;)\;-1) \end{aligned}\)
      - 拓展：若 \(n,m\) 为正整数，则有link(太长就放这里了)。
  - 例题
    - SP4141 ETF - Euler Totient Function | UVA10179 Irreducable Basic Fractions | UVA10299 Relatives
      - 对原数进行分解质因数，顺便求出欧拉函数。
```
int phi(int n)
{
	int ans=n,i;
	for(i=2;i<=sqrt(n);i++)
	{
		if(n%i==0)
		{
			ans=ans/i*(i-1);
			while(n%i==0)
			{
				n/=i;
			}
		}
	}
	if(n>1)
	{
		ans=ans/n*(n-1);
	}
	return ans;
}
```
    - UVA11327 Enumerating Rational Numbers
      - 线性筛欧拉函数（时间复杂度为 \(O(N)\) ）板子
```
void euler(ll n)
{
	memset(vis,false,sizeof(vis));
	phi[1]=1;
	for(ll i=2;i<=n;i++)
	{
		if(vis[i]==false)
		{
			len++;
			prime[len]=i;
			phi[i]=i-1;//phi[i]表示i的欧拉函数
		}
		for(ll j=1;j<=len&&i*prime[j]<=n;j++)
		{
			vis[i*prime[j]]=true;
			if(i%prime[j]==0)
			{
				phi[i*prime[j]]=phi[i]*prime[j];
				break;
			}
			else
			{
				phi[i*prime[j]]=phi[i]*(prime[j]-1);
			}
		}
	}
}
```
- 积性函数
  - 若 \(a,b\) 互质，有 \(f(ab)=f(a) \times f(b)\) ，那么称函数 \(f\) 为积性函数。
  - 性质
    - 若函数 \(f\) 是积性函数，依据算术基本定理，有 \(n=\prod\limits_{i=1}^m p_i^{c_i}\) ，则 \(f(n)=\prod\limits_{i=1}^m f(p_i^{c_i})\) 。