「笔记」数学知识——质数与约数

质数与约数

大概是数学的学习笔记吧，模板、公式之类的太多太杂，于是在这里稍作总结。 才不是想直接复制粘贴现成的模板，不会有太详细的证明过程。
这里是第一篇，之后还会更新…

---

质数

• 定义：若一个正整数无法被1和它本身之外任何自然数整除，称该数为质数（又称素数），反之则为合数。

• 质数的判定： 试除法 太简单了不需要讲

• 质数的筛法

1. 埃氏筛（Eratosthenes）

void get_primes(int n){
    memset(vis,0,sizeof(vis));
    for(int i=2;i<=n;i++){
        if(vis[i]) continue;
        prime[++cnt]=i;
        for(int j=i;j<=n/i;j++) vis[i*j]=1;
    }
}

2. 线性筛法（一般不会用到）
   原理：从小到大累积质因子，防止重复标记合数

void get_primes(int n){
    memset(vis,0,sizeof(vis));
    for(int i=2;i<=n;i++){
        if(!vis[i]){
            vis[i]=i;
            prime[++cnt]=i;
        }
        for(int j=1;j<=cnt;j++){
            //i有更小的质因子或超出范围
            if(prime[j]>vis[i]||prime[j]>n/i) break;
            vis[i*prime[j]]=prime[j];
        }
    }
}

• 质因数分解

1. 算数基本定理 ：任何一个大于1的整数都能被分解为有限个质因数的乘积

$N={p_1}^{c_1}{p_2}^{c_2}\cdots{p_m}^{c_m}\\其中c_i\in\mathbb{N^*}，p_i均为质数，且p_1<p_2<\cdots<p_m$

2. 试除法

void divide(int n){
    for(int i=2;i<=sqrt(n);i++){
        if(n%i==0){//根据质数的筛法，i一定为质数
            p[++cnt]=i;
            c[cnt]=0;
            while(n%i==0) n/=i,c[cnt]++;
        }
    }
    if(n>1) p[++cnt]=n,c[cnt]=1;//不为1表示未除尽，n为质数
}

---

约数

基础内容

• 定义： 整数 d 能整除整数 n ，称 d 为 n 的约数， n为 d 的倍数，记作$d\mid n$

• 整除有关性质：

1. $如果a\mid b且b\mid c，那么a\mid c$

2. $a\mid b且a\mid c\Leftrightarrow a\mid (b\cdot x+c\cdot y)，且\ \ x,y\in \mathbb{Z}$

3. $设m\ne0，则有\ \ a\mid b\Leftrightarrow (m\cdot a)\mid (m\cdot b)$

4. $若满足\ \ ax+by=1，x,y\in \mathbb{Z} 且\ \ a\mid n，b\mid n，那么(a\cdot b)\mid n$

• 算数基本定理的推论

1. N 的正约数的集合可写作：

$\lbrace {p_1}^{b_1}{p_2}^{b_2}\cdots{p_m}^{b_m} \rbrace,0\leq b_i \leq c_i$

2. N 的正约数个数：

$(c_1+1)\cdot(c_2+1)\cdots(c_m+1)=\prod_{i=1}^{m}{(c_i+1)}$

• 求 N 的正约数合集
  可用试除法求得，一个整数 N 的约数个数上界为 $2\sqrt N$

• 求 1 ~ N 中每个数的正约数集合：
  倍数法（时间复杂度 $O(N \log N)$）
  倍数法推论：1 ~ N 中每个数的约数个数的总和约为 $N \log N$

void fac(int n){
    vector<int> factor[N];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n/i;j++){
            factor[i*j].push_back(i);//i*j有约数i
        }
    }
}

最大公约数与最小公倍数

• 定理

$\forall a,b\in \mathbb{Z},\quad \gcd(a,b)\cdot lcm(a,b)=a\cdot b$

• 最大公约数的求法

1. 更相减损法

$\forall a,b\in \mathbb{N},a\geq b,\quad \gcd(a,b)=\gcd(b,a-b)=\gcd(a,a-b)$

$\forall a,b\in \mathbb{N},\quad \gcd(2a,2b)=\gcd(a,b)$

2. 欧几里得法

$\forall a,b\in \mathbb{N},b{\neq}0,\quad \gcd(a,b)=\gcd(b,a \bmod b)$

int gcd(int a,int b){
    if(b==0) return a;
    return gcd(b,a%b);
}

欧拉函数

• 互质
  定义：$\forall a,b\in\mathbb{N}，若\gcd(a,b)=1,称为a,b互质$。

• 定义
  $1 \sim N$ 中与 N 互质的数的个数为欧拉函数，记为$\varphi (n)$

• $\varphi(n)$的计算
  在基础算术定理中，有 $N={p_1}^{c_1}{p_2}^{c_2}\cdots{p_m}^{c_m}$ ，可由容斥原理得

  $\varphi(N)=N\cdot (1-\frac{1}{p_1})\cdot(1-\frac{1}{p_2})\cdots(1-\frac{1}{p_m})$

  代码实现时，我们只需分解质因数就能求出欧拉函数

  int phi(int n){
  int ans=n;
  for(int 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;
  }

• 性质

1. $\forall n>1，1\sim N\ \ 中与N互质的数的和为 \cfrac{n\cdot \varphi(n)}{2}$
2. $若\ \ a,b\ \ 互质，则\ \ \varphi(ab)=\varphi(a)\cdot \varphi(b)$
3. $设质数\ \ p，若 \ \ p\mid n\ \ 且\ \ p\mid n^2，则\ \ \varphi(n)=\varphi(n/p)\cdot p$
4. $设质数\ \ p，若 \ \ p\mid n\ \ 且\ \ p\nmid n^2，则\ \ \varphi(n)=\varphi(n/p)\cdot (p-1)$
5. $\displaystyle \sum_{d\mid n}\varphi(d)=n$

• 欧拉筛
  求 $1$ ~ $n$ 所有的欧拉函数，通过以上积性函数的一些性质可得到线性欧拉筛

  void get_phi(int n){//类似线性质数筛
      phi[1]=1;
      for(int i=2;i<=n;i++){
          if(!vis[i]){
              phi[i]=i-1;
              prime[++m]=i;
          }
          for(int j=1;prime[j]*i<=n;j++){
              vis[prime[j]*i]=1;
              if(i%prime[j]==0){//p能整除(i*p)^2
                  phi[i*prime[j]]=prime[j]*phi[i];
                  break;
              }
              else phi[i*prime[j]]=(prime[j]-1)*phi[i];
          }
      }
  }

END

打赏