数论讲解（数论笔记）

♠ use C++11 ♠ tip: 函数内必须是用变量来传输引用形参

倍数

若 \(a,b,k \in \mathbb N\)  
  
  
  
  
  
  ，且 \(a \times k=b\) 
  
  
  
  
  
  
 ，那么 \(b\) 是 \(a\) 的倍数


 


 


 


 


 


 


，称 \(a\) 整除 \(b\) 
 
 
 
 
 
 ，记作 \(a \mid b\)              。

\([1,n]\in \mathbb N\) 中 \(x \in \mathbb N\) 的倍数有 \(\left \lfloor \dfrac{n}{x} \right \rfloor\) 个 
 
  
 
  
 
  
 
  
 
  
 
  
 
。

约数

若 \(a \mid b\)  
   
   
   
   
   
   
 ，\(a,b\in\mathbb N\)

 

 

 

 

 

 

，那么 \(a\) 是 \(b\) 的约数












。

\(a \in \mathbb N\) 的约数个数是有限的
 

 

 

 

 

 

 ，记作 \(\operatorname d(n)\)              ，\(\in \mathbb Z\)
  
  
  
  
  
  
  。

快速算一个序列的 \(\operatorname d(n)\)：设一个计数数组对应每个数
 

 
 

 
 

 
 

 
 

 
 

 
 

，初始为 0












，从左到右计算每个数                     ，对于每个倍数加 1
 
 
 
 
 
 
 
 
 
 
 
 
 
，当整个序列计算完后



















，计数数组的值是其对应数字的约数个数              ，时间复杂度 \(\mathcal{O}(n\operatorname{log}n)\) 
  
  
  
  
  
  
。下面是一个例子以及代码实现：

n 1 2 3 4 5 6 d(n) 0 0 0 0 0 0 start +1 +1 +1 +1 +1 +1 step 1 in number 1 0 +1 0 +1 0 +1 step 2 in number 2 0 0 +1 0 0 +1 step 3 in number 3 .....and more 1 2 2 3 2 4 end void approximate_number(long long *num,long long &to){ for(long long i=1;i<=to;++i){ for(long long j=i;j<=to;j+=i){ (*(num+j))++; } } }

素数

1 不是素数也不是合数 


 


 


 


 


 


 

。

下面是一串判断 \(n\in \mathbb N\) 是否是素数的代码
 
  
 
  
 
  
 
  
 
  
 
  
 
 ，时间复杂度 \(\mathcal{O}(\sqrt n)\)
 
 
 
 
 
 
 。

bool is_prime(long long &n){ if(n==1) return false; for(long long i=2;i<=n/i;++i){ if(n%i==0) return false; } return true; } 计算一个序列每个数是否是素数：朴素筛法













，有较多重复判断  
  
  
  
  
  
  ，时间复杂度 \(\mathcal{O}(n\operatorname{log}n)\)；埃式筛法 
  
  
  
  
  
  
 ，仅是素数才向后筛


 


 


 


 


 


 


，优化朴素筛法 
 
 
 
 
 
 ，时间复杂度 \(\mathcal{O}(n\operatorname{log log}n)\)  
   
   
   
   
   
   
 ，接近线性筛  
   
   
   
   
   
   
。

最大公约数

若 \(a,b\in \mathbb N\) 且 \(k \mid a,b \in \mathbb N\)

 

 

 

 

 

 

，且不存在更大的 \(k\)
 

 

 

 

 

 

 ，称 \(k\) 是 \(a,b\) 的最大公约数 

 

 

 

 

 

 
。

快速求 \(a,b\in \mathbb N\) 的最大公约数              ，欧几里得定理：\(\gcd(a,b)=\gcd(b,a \bmod b)\)

 

 

 

 

 

 

 。

已知 \(a,b \in \mathbb N\)
 

 
 

 
 

 
 

 
 

 
 

 
 

，可找到 \(x,y \in \mathbb Z\) 使 \(ax +by=\gcd(a,b)\)












，若 \(ax+by=1\) 有解                     ，则 \(a\) 和 \(b\) 互质             。

扩展欧几里得
 
 
 
 
 
 
 
 
 
 
 
 
 
，一定存在 \(x,y\in \mathbb N\) 使贝祖等式 \(ax +by=\gcd(a,b)\)\(\Rightarrow (\left \lfloor a \div b \right \rfloor \times b + a \bmod b) x + by = \gcd(b,a\bmod b)\)\(\Rightarrow (\left \lfloor a \div b \right \rfloor \times x + y) b +(a \bmod b)x\)



















，可得新的方程 \(b \times x+(a \bmod b)\times y = \gcd(b,a\bmod b)\) 因此可得 \(\begin{cases}x=(\left \lfloor a \div b \right \rfloor\times x+y)\\y=x\end{cases}\)              ，同样倒推可得特解 \(\begin{cases}x=y\\y=x-(\left \lfloor a \div b \right \rfloor\times y)\end{cases}\)
 
  
 
  
 
  
 
  
 
  
 
  
 
 ，下面是递归代码实现：

array<long long,3> exgcd(long long &a,long long &b){ if(b==0){ return {1,0,a}; //当b=0时













，等式为ax=gcd(a,0)  
  
  
  
  
  
  ，即ax=a //得x=1,y=0 } array<long long,3> ans=exgcd(b,a%b); long long temp=ans[0]; ans[0]=ans[1]; ans[1]=temp-a/b*ans[1]; return ans;//ans[0]为x 
  
  
  
  
  
  
 ，ans[1]为y


 


 


 


 


 


 


，ans[2]为gcd(a,b) } 当求得贝祖等式特解 \(x_0,y_0\in \mathbb N\) 后 
 
 
 
 
 
 ，可得 \(x,y\in \mathbb N\) 通解  
   
   
   
   
   
   
 ，设 \(g=\gcd(a,b)\) 通解为 \(\begin{cases}x=x_0+t\times b\div g\\y = y_0- t \times a \div g\end{cases}\)

 

 

 

 

 

 

，推导过程：\(\begin{cases}ax+by=g\\ax_0+bx_0=g\end{cases}\)\(\Rightarrow (x-x_0)a+(y-y_0)b=0\)\(\Rightarrow (x-x_0)a=(y_0-y)b\)\(\Rightarrow (x-x_0)\dfrac{a}{g}=(y_0-y)\dfrac{b}{g}\)\(\Rightarrow \begin{cases}x-x_0=t\times \dfrac{b}{g}\\y_0-y=t \times \dfrac{a}{g}\end{cases}\)\(\Rightarrow \begin{cases} x=x_0+t\times\dfrac{b}{g}\\y=y_0-t\times\dfrac{a}{g}\end{cases}\)
 

 

 

 

 

 

 ，其中 \(x\) 的第一个解是 \(\bigg(x\bmod\dfrac{b}{g}+\dfrac{b}{g}\bigg)\bmod \dfrac{b}{g}\) 
 

 
 

 
 

 
 

 
 

 
 

 
 
。

模运算

已知 \(a,b,p\in \mathbb N\)              ，\((a+b)\bmod p=(a\bmod p+b\bmod p)\bmod p\)
 

 
 

 
 

 
 

 
 

 
 

 
 

，\((a-b)\bmod p=(a\bmod p+b\bmod p)\bmod p\)












，\((a\times b)\bmod p=(a \bmod p\times b\bmod p)\bmod p\)













。

若需要进行除法的模运算                     ，与普通的不同
 
 
 
 
 
 
 
 
 
 
 
 
 
，例子：\(\dfrac{20}{10}\bmod 5=2\)\(\nRightarrow\dfrac{20 \bmod 10}{10\bmod 10}\bmod 5=0\)



















，所以为了求 \((a\div b) \bmod p\)              ，\(a,b,p\in\mathbb N\)
 
  
 
  
 
  
 
  
 
  
 
  
 
 ，需要找到 \(b\) 的乘法逆元 \(x\in\mathbb N\)













，将算式变成 \((a\times x)\bmod p\)                    。

已知 \(a,x,m\in \mathbb N\)  
  
  
  
  
  
  ，\(ax \equiv 1\pmod p\)\(\Rightarrow ax \bmod p=1\)\(\Rightarrow ax-\left\lfloor\dfrac{ax}{p}\right\rfloor\times p=1\) 
  
  
  
  
  
  
 ，称 \(x\) 是关于 \(a\) 的乘法逆元


 


 


 


 


 


 


，将 \(-\left\lfloor\dfrac{ax}{p}\right\rfloor\) 用 \(y\) 替代 
 
 
 
 
 
 ，得 \(ax+py=1\),即找到 \(x\) 的值即可找到 \(a\) 的乘法逆元  
   
   
   
   
   
   
 ，也可知 \(a,p\) 必须要互质 
 
 
 
 
 
 
 
 
 
 
 
 
 
。