数论杂记

前言

原本打算将这篇博客取名数论基础，然而想想实在狂妄，本文仅仅记录了一些在做编程题时可能会用到的数学方法，离正统的数论还相差甚远，就数论杂记一名仍有蹭热度之嫌，不甚惶恐，留下这篇杂记。

最大公约数 —— Greatest Common Divisor(GCD)

朴素的暴力法求最大公约数和辗转相除法的思想这里都不做赘述，我们仅仅介绍两种超快的求最大公约数算法：

1. 位运算法（a*b!=0）

   int gcd(int a,int b)
   {
     while(b^=a^=b^=a%=b);
     return a;
   }

2. if+while+位运算法

   int gcd(int a,int b)
   {
     if(b) while((a%=b)&&(b%=a));
     return a+b;
   }

质数判断

朴素的暴力法这里不再赘述，我们仅仅介绍一种超快的判断质数方法：

bool prime(int num)
{
  if(num==1)  return false;
  if(num==2||num==3)  return true;
  if(num%6!=1&&num%6!=5)  return false;
  int tmp=sqrt(num);
  for(int i=5;i<=tmp;i+=6)
    if(num%i==0||num%(i+2)==0)
      return false;
  return true;
} 

分解质数

已知一个数可以分解成1和其本身相乘形式、或一种确定的若干个的质数相乘的形式，我们可以设计一种算法统计这些形式的长度（其中不包括1）：

int sum(int i)
{
  int n=0,m=2;
  while(i!=1&&m<=sqrt(i))
  {
    while(i%m==0)
    {
      n++;
      i/=m;
    }
    m++;
  }
  if(i!=1)  n++;
  return n;
}

我们也可以设计一个朴素的算法来输出这个序列：

void prim(int m)
{
    int n = 2;
    while(m>=n)
    {
        while(m%n) n++;
        cout<<n<<" ";
        m/=n;
    }
    cout<<endl;
}

约数个数

在上文中我们提到了任何一个数都可以分解为质数相乘的形式，我们很容易联想到一个数的约数个数会和其质数数量存在某种联系，实际上也确实如此：

一个数约数的个数等于其分解成的各个质数的幂次数加一之和的积。

最小公倍数

对于最小公倍数的计算，我们首先可以基于gcd的基础得到一个简单的算法：

int ans(int a,int b)
{
  return a*b/gcd(a,b);
}

我们还可以根据上文的约数分解逆推出求其最小公倍数的公式，我们知道如果某个数a含有约数b，那么数a的倍数也含有这个约数b，因此有结论：

最小公倍数等于各个数字分解而成的各个质数在所有数字中最大幂次的积。

大数运算