♠ use C++11

倍数

  1. 若 \(a,b,k \in \mathbb N\)，且 \(a \times k=b\)，那么 \(b\) 是 \(a\) 的倍数，称 \(a\) 整除 \(b\)，记作 \(a \mid b\)。

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

约数

  1. 若 \(a \mid b\)，那么 \(a\) 是 \(b\) 的约数。

  2. \(a \in \mathbb N\) 的约数个数是有限的，记作 \(\operatorname d(n)\)。

  3. 快速算一个序列的 \(\operatorname d(n)\)：设一个计数数组对应每个数，初始为 0，从左到右计算每个数，对于每个倍数加 1，当整个序列计算完后，计数数组的值是其对应数字的约数个数，时间复杂度 \(\mathcal{O}(n\operatorname{log}n)\)。下面是一个例子：

n    1 2 3 4 5 6d(n) 0 0 0 0 0 0 start     1 1 1 1 1 1 step 1 in number 1     1 2 1 2 1 2 step 2 in number 2     1 2 2 2 1 3 step 3 in number 3     .....more

素数

  1. 1 不是素数也不是合数。

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

bool is_prime(long long n){if(n==1)return false;for(long long i=1;i<=n/i;++i){if(x%i==0)return false;}return true;}
  1. 计算一个序列每个数是否是素数：朴素筛法，有较多重复判断，时间复杂度 \(\mathcal{O}(n\operatorname{log}n)\)；埃式筛法，仅是素数才向后筛，优化朴素筛法，时间复杂度 \(\mathcal{O}(n\operatorname{log log}n)\)，接近线性筛。

最大公约数

  1. 若 \(a,b\in \mathbb N\) 且 \(k \mid a,b\)，且不存在更大的 \(k\)，称 \(k\) 是 \(a,b\) 的最大公约数。

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

  3. 已知 \(a,b \in \mathbb N\)，可找到 \(x,y \in \mathbb Z\) 使 \(ax +by=\gcd(a,b)\)，若 \(ax+by=1\) 有解，则 \(a\) 和 \(b\) 互质。

  4. 扩展欧几里得，一定存在 \(x,y\in \mathbb Z\) 使贝祖等式 \(ax +by=\gcd(a,b)\)\(\Rightarrow (\left \lfloor a \div b \right \rfloor \times b + a \bmod b) x + b \times y = \gcd(b,a\bmod b)\)\(\Rightarrow (\left \lfloor a \div b \right \rfloor \times x + y) b +(a \bmod b)\times 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 exgcd(int a,int b){if(b==0){return {1,0,a};//当b=0时，等式为ax=gcd(a,0)，即ax=a//得x=1,y=0}array ans=exgcd(b,a%b);int 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)}
  1. 当求得贝祖等式特解 \(x_0,y_0\in \mathbb Z\) 后，可得 \(x,y\in \mathbb Z\) 通解，设 \(g=\gcd(a,b)\) 通解为 \(\begin{cases}x=x_0+b\div g \times t\\y = y_0+a \div g \times t\end{cases}\)，推导过程：$$