数学知识小结#1

PREFACE

时隔数月尝试拾起以往的OI知识发现异常的艰难,于是准备慢慢的填坑,可能比较简略并且穿插不少英文(万一面试的时候问起OI还能说几句pao),但是我英语太菜了，如果您发现了错误或是需要改进的地方，欢迎联系我或是在下方评论

小结#1主要是数论部分，小结#2到时看情况在更吧

update:里面的除法都是指下取整

质数与约数Prime Number&Divisors

质数筛法Sieve

  • 埃拉托斯特尼筛法Sieve of Eratosthenes
    主要思想是任意整数x的倍数2x,3x…都不是质数
    由于在筛x的倍数时,小于$x^2$的数已经被筛过(显然),我们直接从$x^2$开始筛

    1
    2
    3
    4
    5
    6
    7
    void EratosthenesSieve(int n){
    	memset(vis,0,sizeof(vis));
        for(int i=2;i<=n;i++){
        	if(vis[i])continue;
          	for(int j=i*i;j<=n;j+=i)vis[j]=1;
        }
    }

  • 欧拉线性筛Euler’s Linear Sieve

    埃式筛在筛一些数时还是会重复(比如12会被2和3同时筛一遍)，但是只要我们让我们要筛的数的质因子从小到大累计，即每个数只会被它的最小质因子筛一次，这样的话每个数只会被筛一次，复杂度就是线性的了

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    void EulerSieve(int n){
        memset(vis,0,sizeof(vis));
        memset(prime,0,sizeof(prime));
        cnt=0;
        for(ri i=2;i<=n;i++){
            if(vis[i]==0){//i is a prime number
                prime[++cnt]=i;
            }
            for(ri j=1;j<=cnt&&prime[j]*i<=n;j++){
                vis[i*prime[j]]=1;
                if(i%prime[j]==0)break;//now i can be divided by prime[j],so prime[j+1] is not the least prime divisor of the i*prime[j+1]
            }
        }
    }

质因数分解Prime Factorization

  • 算术基本定理Fundamental Theorem Of Arithmetic

    也称为唯一分解定理(unique factorization theorem),是指任何一个大于1的正整数都能被唯一分解为有限个质数的乘积,可写作

    其中$p_i$是质数且$p_1<p_2<…<p_m$

    Every positive integer n>1 can be represented in exactly one way as a product of prime powers

    where $p_1<p_2<…<p_m$ are primes and the $n_i$ are positive intergers.

    (来源: 维基百科)

最大公约数Greatest Common Divisors

  • 定义:

    根据字面意思,自然数$a$和$b$的公约数中最大的d就是a和b的最大公约数,称为$gcd(a,b)$

  • 定理:

    $gcd(a,b)$*$lcm(a,b)=a$*$b $

  • 更相减损法

    $\forall a>b,a,b \in N$ $gcd(a,b)=gcd(a,a-b)=gcd(b,a-b)$

  • 辗转相除法

    $\forall a,b \in N$ $gcd(a,b)=gcd(b,a \mod b)$

积性函数相关Multiplicative Funtion

  • 积性函数定义:

    若对任意互质$a,b$(即$gcd(a,b)=1$),有$f(ab)=f(a)f(b)$,则称函数$f$为积性函数

    特殊地,若对任意正整数都有$f(ab)=f(a)$ * $f(b)$,则称函数$f$为完全积性函数(Completely Multiplicative Function)

    显然若$N=p_1^{c_1}p_2^{c_2}…p_m^{c_m}$,则$f(N)= \prod_{i=1}^m f(p_i^{c_i})$

    于是求一个积性函数我们可以设法套用筛法求出

  • 欧拉函数(Euler Tocient Funciton)定义:

    在$1$到$N$中与$N$互质的数的个数称为欧拉函数,记作$\phi(N)$

    若$N=p_1^{c_1}p_2^{c_2}…p_m^{c_m}$

    则$\phi(N)=N$*$\frac{p_1-1}{p_1}$*$\frac{p_2-1}{p_2}$*$…$*$ \frac{p_m-1}{p_m}$

    这个式子可以由容斥原理(The Principle Of Inclusion-exclusion)推得

  • 欧拉函数性质

    • 对于一个质数N,$\phi(N)=N-1$

    • 对于$N=p^k$($p$是质数),$\phi(N)=p^k-p^{k-1}$

      简要证明:此时只有$p,2p,3p…$等$p^{k-1}$个数与$N$不互质

    • $\sum_{d|n} \phi(d)=n$

      简要证明:设$f(n)=\sum_{d|n} \phi(d)$，发现它是个积性函数

      又因为$f(p_i^{c_i})=\phi (1) + \phi (p)+…+\phi (p_i^{c_i})$根据上一条性质,就等于$p_i^{c_i}$

      于是$f(n)= \prod_{d|n} f(p_i^{c_i}) = \prod p_i^{c_i} =n$

    • $\phi(n)=\sum_{d|n} \mu(d) \frac{n}{d}$

      简要证明: 莫比乌斯反演,见下

  • 莫比乌斯函数(Mobious Function)定义

    设正整数$N=p_1^{c_1}p_2^{c_2}…p_m^{c_m}$

    定义函数
    $\mu(n)= \begin{cases} (-1)^m & \text{when $c_1=c_2=…=c_m=1$,}\\ 0 & \text{otherwise} \end{cases}$

    为莫比乌斯函数

    它有个比较有用的性质

    $\sum_{d|n}\mu(d)=[n=1]$

    它也是积性函数,于是我们可以运用欧拉线性筛求出$1-N$的莫比乌斯函数

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    void Mobious(int n){
      memset(vis,0,sizeof(vis));
      mu[1]=1;
      for(ri i=2;i<=n;i++){
          if(vis[i]==0){//prime number
              mu[i]=-1;
              prime[++cnt]=i;
          }
          for(ri j=1;j<=cnt&&prime[j]*i<=n;j++){
              vis[prime[j]*i]=1;
              if(i%prime[j]==0){
                  mu[i*prime[j]]=0;//c_i !=1
                  break;
              }
              mu[i*pri[j]]=-mu[i];
          }
      }
    }

  • 数论函数(Arithmetic Funtion)

    似乎也可以说Number Theoretic Function,是指定义域为正整数的函数

    A number theoretic funtion is a function whose domain is the set of positive integers

  • 莫比乌斯反演公式(Mobius Inversion Formula)

    对于两个数论函数$F(n)$和$f(n)$,且满足

    $F(n)=\sum_{d|n} f(d)$

    那么$f(n) = \sum_{d|n} \mu(d) F(\frac{n}{d})$

    简要证明:

    $\sum_{d|n} \mu(d) F(\frac{n}{d})=\sum_{d|n} \mu(d) \sum_{i|{\frac{n}{d}}} f(i)$

    对于第二个式子,我们考虑每个$f(i)$对几个$\mu(d)$作贡献,发现等价于

    $\sum_{i|n} f(i) \sum_{d|{\frac{n}{i}}} \mu(d)$

    再由$\sum_{d|n}\mu(d)=[n=1]$,得只有i=n时后面的sigma不是0,也就是等于$f(n)$

    现在让我们证明前文提到的这个式子$\phi(n)=\sum_{d|n} \mu(d) \frac{n}{d}$

    先引入一个$id$函数,$id(n)=n$

    $\because id(n) = n = \sum_{d|n} \phi(d)$

    $\therefore \phi(d) = \sum_{d|n} \mu(d) id(\frac{n}{d}) = \sum_{d|n} \mu(d) \frac{n}{d}$

  • 狄利克雷卷积(Dirichlet Convolution)

    两个数论函数f和g的卷积为$(f ∗ g)(n)=\sum_{d|n} f(d)g(\frac{n}{d})$ ,后面的括号可以省略不写

    满足交换律,结合律,分配律

    两个积性函数的卷积依然为积性函数

    前面的莫比乌斯反演也可以通过狄利克雷卷积证明

同余Modular Arithmetic

定义

若整数$a$与$b$除以正整数n的余数相等,则称$a,b$模$n$同余,记为$a \equiv b \pmod n$

“For a positive integer n, two numbers a and b are said to be congruent modulo n, if their difference a-b is an integer multiple of n(that is , if there is an integer $k$ such that a-b = kn),and is denoted $a \equiv b \pmod (n)$.

The number n is called the modulus of the congruence.”

来源:维基百科

费马小定理Fermat’s Little Theorem

若$p$是质数,则对任意正整数$a$,有$a^p \equiv a \pmod p$

欧拉定理Euler Theorem