数学知识小结#1

PREFACE

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

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

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

质数与约数Prime Number&Divisors

质数筛法Sieve

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

    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同时筛一遍)，但是只要我们让我们要筛的数的质因子从小到大累计，即每个数只会被它的最小质因子筛一次，这样的话每个数只会被筛一次，复杂度就是线性的了

    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的正整数都能被唯一分解为有限个质数的乘积,可写作

    [N=p_1^{c_1}p_2^{c_2}...p_m^{c_m} ]

    其中(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

    [N=p_1^{c_1}p_2^{c_2}...p_m^{c_m} ]

    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)= egin{cases} (-1)^m & ext{when (c_1=c_2=…=c_m=1),} 0 & ext{otherwise} end{cases}$

    为莫比乌斯函数

    它有个比较有用的性质

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

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

    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)

    (ecause id(n) = n = sum_{d|n} phi(d))

    ( herefore 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

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/Rye-Catcher/p/10847143.html