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

HZOI - Isaac / 2023-08-18 / 原文

前置知识

质数的个数是无限的。
试除法：若一个正整数 \(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(太长就放这里了)。
- 若 \(n\) 为正整数，则 \(\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} [\gcd(i,j) \in \mathbb{P}]= \sum\limits_{d \in \mathbb{P}}^{n}\;(\;2 \times \;(\;\sum\limits_{i=1}^{\dfrac{n}{d}}\varphi(i)\;)\;-1)\) ；其中 \(\mathbb{P}\) 表示素数集， \(\mathbb{P}=\{2,3,5,7,11,13,17,19,23,29,...\}\) 。
  - luogu P2568 GCD
  - 证明：
    
    \(\begin{aligned}\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} [\gcd(i,j) \in \mathbb{P}] \end{aligned}\)
    
    \(\begin{aligned}&=\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} \sum\limits_{d\in \mathbb{P}}^{n}[\gcd(i,j)=d] \end{aligned}\)
    
    \(\begin{aligned}&=\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} \sum\limits_{d\in \mathbb{P}}^{n} [\gcd(\dfrac{i}{d},\dfrac{j}{d})=1] \end{aligned}\)
    
    \(\begin{aligned}&=\sum\limits_{d\in \mathbb{P}}^{n} \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\in \mathbb{P}}^{n} \;(\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 \in \mathbb{P}}^{n} \;(\;(\;\sum\limits_{i=1}^{\dfrac{n}{d}} \times 2 \times \varphi(i)\;)\;-1) \end{aligned}\)
    
    \(\begin{aligned}&=\sum\limits_{d \in \mathbb{P}}^{n}\;(\;2 \times \;(\;\sum\limits_{i=1}^{\dfrac{n}{d}}\varphi(i)\;)\;-1) \end{aligned}\)

例题

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})\) 。