关于质数和约数的一个小总结

约数

定义

​ 若整数n能够整除d,则d是n的约数,n是d的倍数,记作d|n

基本性质

  • 唯一分解定理:任何一个正整数都可以分解为$p_1^{b_1}p_2^{b_2}p_3^{b_3}……p_n^{b_n}$(为了后面的叙述,若$i<j,p_i<p_j$)
  • 它的正约数个数:$\prod_{i=1}^{m}(b_i+1)$
  • $lcm(a,b)gcd(a,b)=ab$

基本算法和板子

  • 试除法: 用来求解一个数的正约数集合,时间复杂度:$\Theta(\sqrt n)$
  • 更相减损术: 当使用高精度的时候,使用它来求解最大公约数很方便
int gcd(int x,int y){
return (!y)?x:gcd(y,x-y);
}
  • 辗转相除法:比更相减损术更快

    int gcd(int x,int y){
    return (!y)?x:gcd(y,x%y);
    }

    当然了,有一个速度更快的二进制版本

    inline int gcd(int x,int y){
    int i,j;
    if(x==0)return y;
    if(y==0)return x;
    for(i=0;(x&1)==0;i++)x>>=1;
    for(j=0;(y&1)==0;j++)y>>=1;
    if(i>j)i=j;
    while(true){
    if(x<y){x^=y;y^=x;x^=y;}
    if(!(x%=y))return y<<i;
    while(!(x&1))x>>=1;
    }
    }

素数

定义

这个很简单吧,小学就学过的

基本定理

  • 唯一分解定理(同上)
  • 威尔逊定理:如果$(p-1)!\equiv-1(mod\ p)$,则p为质数
  • 质数有无穷多个
  • 欧拉定理这些的就放在同余那一块来讲了

数论的板子都在这里面来看吧

数论板子