整除

定义与性质

设$a,b\in \Z,a\neq0$，若$\exists q\in \Z$，使得$b=aq$，那么说b可被a整除，记作$a|b$

$a\mid b \iff -a\mid b \iff a\mid -b \iff |a|\mid |b|$
$a\mid b \wedge b\mid c \implies a\mid c$
$a\mid b \wedge a\mid c \iff \forall x,y\in\mathbb{Z},\;a\mid(xb+yc)$
$a\mid b \wedge b\mid a \implies b=\pm a$
设 $m\neq0$，那么
\[ a\mid b \iff ma\mid mb \]
设 $b\neq0$，那么
\[ a\mid b \implies |a|\le|b| \]
设 $a\neq0,\;b=qa+c$，那么
\[ a\mid b \iff a\mid c \]

约数

定义：若$a|b$，则$b$是$a$的倍数，$a$是$b$的约数

性质：

0是所有非0正数的倍数，对于整数$b \neq a$，b的约数只有有限个
平凡约数：对于整数$b\neq 0$，±1、±b是b的平凡约数

当$b=±1$时，只有两个平凡约数
真约数：b的其他约数
- $b\neq 0$，当d遍历b的全体约数时，$\frac{b}{d}$也遍历b的全体约数
- $b>0$，则当d遍历b时全体正约数时，$\frac{b}{d}$也遍历b的全体约数

没有特殊说明，约数总是指向正约数

余数

设$a,b$为两个给定的整数，$a\neq0$. 设$d$是一个给定的整数，则一定存在唯一一对整数$q$与$r$，满足$b=qa+r$，$q=\lfloor\frac{b}{a} \rfloor ,d\leq r<|a|+d$

其中这里的d表示不同取值区间的余数，无论整数d取何值，r统称余数，$a|b$等价于$a|r$

带余数除法

一般情况下，$d=0$，此时$b=qa+r$，$0\leq r<|a|$称为带余数除法，余数r称为最小非负余数，如果没有特别说明，余数总是指最小非负余数

r可以写成$r=b\bmod{a}$

余数的性质

任一整数被正整数a除后，余数一定是且仅是0到(a-1)这a个数中的一个
相邻的a个整数被正整数a除后，恰好取到上述a个余数，特别的，一定有且仅有一个数被a整除

最大公约数与最小公倍数

最大公约数

定义

一组整数的公约数，是指同时是这组数中每一个数的约数的数。$\pm 1$ 是任意一组整数的公约数。一组整数的最大公约数，是指所有公约数里面最大的一个。写作gcd(a,b)

性质

$\displaystyle \gcd(a_1,\dots,a_n)=\gcd\bigl(|a_1|,\dots,|a_n|\bigr)$
$\displaystyle \gcd(a,b)=\gcd(b,a)$
若 $a\neq0$，则 \[\gcd(a,0)=\gcd(a,a)=|a|.\]
$\displaystyle \gcd(bq+r,\;b)=\gcd(r,\;b)$
$\displaystyle \gcd(a_1,\dots,a_n) =\gcd\bigl(\gcd(a_1,a_2),a_3,\dots,a_n\bigr).$
进而对任意 $1<k<n$，都有
\[ \gcd(a_1,\dots,a_n) =\gcd\!\bigl(\gcd(a_1,\dots,a_k)\,,\,\gcd(a_{k+1},\dots,a_n)\bigr). \]
对不全为 0 的整数 $a_1,\dots,a_n$ 和非零整数 $m$，
\[ \gcd(m a_1,\dots,m a_n) =|m|\;\gcd(a_1,\dots,a_n). \]
对不全为 0 的整数 $a_1,\dots,a_n$，若 $\gcd(a_1,\dots,a_n)=d$，则
\[ \gcd\bigl(a_1/d,\dots,a_n/d\bigr)=1. \]
$\displaystyle \gcd\bigl(a^n,b^n\bigr)=\bigl(\gcd(a,b)\bigr)^n.$
若 $b\mid ac$ 且 $\gcd(a,b)=1$，则 $b\mid c.$
若 $b\mid c,\;a\mid c$ 且 $\gcd(a,b)=1$，则 $ab\mid c.$
若 $\gcd(a,b)=1$，则 $\gcd(a,bc)=\gcd(a,c).$
若 $\gcd(a_i,b_j)=1,\;\forall\,1\le i\le n,\;1\le j\le m$，则
\[ \gcd\Bigl(\prod_{i=1}^n a_i\,,\,\prod_{j=1}^m b_j\Bigr)=1. \] 特别地，若 $\gcd(a,b)=1$，则
\[ \gcd(a^n,b^m)=1. \]
对整数 $a_1,\dots,a_n$，若存在 $v\in\mathbb{Z}$ 使
\[ \prod_{i=1}^n a_i = v^m, \] 且对任意 $i\neq j$ 有 $\gcd(a_i,a_j)=1$，则
\[ \forall\,1\le i\le n,\quad \sqrt[m]{a_i}\in\mathbb{Z}_0. \]

求法

欧几里得算法

对于正整数$a,b$，有$\gcd(a,b)=\gcd(b, a\bmod{b})$

代码实现如下：

递归版

ll gcd(ll a,ll b){
	return b==0?a:gcd(b,a%b);
}

位运算版

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

多个数求gcd，答案一定是每个数的约数，那么也一定是每相邻两个数的约数。我们采用归纳法，可以证明，每次取出两个数求出答案后再放回去，不会对所需要的答案造成影响。

扩展欧几里得算法

exgcd是用来求形如$ax+by=\gcd(a,b)$的一组可行解的算法

证明略，一组可行解形如$x_1=y_2,y_1=x_2-\lfloor\frac{a}{b} \rfloor y_2$

$b=0$时，显然有$\gcd(a,0)=a$，则一组解为$x=1, y=0$

代码：

ll exgcd(ll a,ll b,ll &x,ll &y){
	if(b==0){
		x=1; y=0;
		return a;
	}
	ll d=exgcd(b,a%b,x,y);
	ll t=x;
	x=y;
	y=t-(a/b)*y;
	return d;
}

更相减损术

这个方法出自九章算术：

~~任意给定两个正整数，判断是否都是偶数，若是，则用2约分，若不是，则执行下一步~~
用较大的数减较小的数，接着将所得差与减数比较，并以大数减小数，操作至所得减数和差相等为止，则该等数就是所求的最大公因数

互素

若$\gcd(a_1,b_1)=1$，称$a_1,a_2$互素，若$\gcd(a_1,\cdots,a_n)=1$称$a_1,\cdots,a_n$互素

多个整数互素，不一定两两互素

快速GCD

预处理

$O(n)$预处理，$O(1)$查询两个小于$n$的数的快速gcd

预处理：

预处理所有$(i,j)$，其中$i,j\leq\sqrt{n}$的gcd，可以以$O(n)$推出
预处理$n$以内质数

查询：

设$x=abc$，则$(x,y)=(a,y)\times\left(b,\dfrac{y}{(a,y)}\right)\times\left(c,\dfrac{y}{(ab,y)}\right)$

若$a\in P$，只需要判断$a$是否整除$y$，否则$(a,y)=(y\bmod a, a)$，因为$a\leq \sqrt{n}$，可查表

const int T = 1000;
const int M = 1000000;

int g[T][T], fac[M][3];
bitset<M> vis;
vector<int> pri;
void prework() {
  vis[0] = vis[1] = true;
  fac[1][0] = fac[1][1] = fac[1][2] = 1;
  for (int i = 2; i < M; ++i) {
    if (!vis[i]) {
      fac[i][0] = fac[i][1] = 1;
      fac[i][2] = i;
      pri.push_back(i);
    }
    for (int j : pri) {
      int mul = i * j;
      vis[mul] = true;
      fac[mul][0] = fac[i][0] * j;
      fac[mul][1] = fac[i][1];
      fac[mul][2] = fac[i][2];
      sort(fac[mul], fac[mul] + 3);
      if (i % j == 0)
        break;
    }
  }
  for (int i = 0; i < T; ++i)
    g[0][i] = g[i][0] = i;
  for (int i = 1; i < T; ++i)
    for (int j = 1; j <= i; ++j)
      g[i][j] = g[j][i] = g[j][i % j];
}
int gcd(int a, int b) {
  int ans = 1;
  for (int i = 0; i < 3; ++i) {
    int _ = fac[a][i] > T ? (b % fac[a][i] ? 1 : fac[a][i])
                          : g[fac[a][i]][b % fac[a][i]];
    b /= _;
    ans *= _;
  }
  return ans;
}

更相减损术

$O(\log{n})$

若$a=b$, $(a,b)=a=b$
若$2|a,2|b$, $(a,b)=\left(\dfrac{a}{2},\dfrac{b}{2}\right)$
若$2\mid a,2\nmid b$, $(a,b)=\left(\dfrac{a}{2},b\right)$
若均不满足，设$a>b$, 则$(a,b)=(a-b,b)$

int gcd(int a, int b) {
  int i = __builtin_ctz(a);
  int j = __builtin_ctz(b);
  int k = min(i, j);
  int d;
  b >>= j;
  while (a) {
    a >>= i;
    d = b - a;
    i = __builtin_ctz(d);
    if (a < b) b = a;
    if (d < 0) a = -d;
    else a = d;
  }
  return b << k;
}

最小公倍数

定义

一组整数的公倍数，是指同时是这组数中每一个数的倍数的数。0是任意一组整数的公倍数。

一组整数的最小公倍数，是指所有正的公倍数里面，最小的一个数。记作lcm(a,b)

性质

$\displaystyle lcm(a_1,\dots,a_n)=lcm(|a_1|,\dots,|a_n|)$
$\displaystyle lcm(a,b)=lcm(b,a)$
若 $a\neq0$，则 $lcm(a,1)=lcm(a,a)=|a|.$
若 $a\mid b$，则 $lcm(a,b)=|b|.$
$\displaystyle lcm(a_1,\dots,a_n) =lcm\bigl(lcm(a_1,a_2),a_3,\dots,a_n\bigr).$
进而对任意 $1<k<n-1$，都有
\[ lcm(a_1,\dots,a_n) =lcm\Bigl(lcm(a_1,\dots,a_k),\;lcm(a_{k+1},\dots,a_n)\Bigr). \]
若 $a_i\mid m,\ \forall\,1\le i\le n$，则
\[ lcm(a_1,\dots,a_n)\mid m. \]
$\displaystyle lcm(ma_1,\dots,ma_n)=|m|\;lcm(a_1,\dots,a_n)\,.$
$\displaystyle lcm(a,b,c)\,lcm(ab,bc,ca) =lcm(a,b)\,lcm(b,c)\,lcm(c,a)\,.$
$\displaystyle lcm(a^n,b^n)=\bigl(lcm(a,b)\bigr)^n\,.$

求法

两个数：$\gcd(a,b)\times lcm(a,b)=a\times b$

代码

ll lcm(ll a,ll b){
	return a/gcd(a,b)*b; // 防止 a*b 爆 ll，所以先 /gcd 再 *b
}

多个数：我们其实没有必要求一个共同的最大公约数再去处理，最直接的方法就是，当我们算出两个数的 gcd，或许在求多个数的 gcd时候，我们将它放入序列对后面的数继续求解，那么，我们转换一下，直接将最小公倍数放入序列即可。

素数与合数

见质数

算术基本定理

内容

算术基本引理：设p是素数，$p|a_1a_2$，那么$p|a_1$与$p|a_2$至少有一个成立

唯一分解定理：设正整数a，则必有表示$a=p_1p_2\cdots p_s$，其中$p_j(1\leq j\leq s)$是素数，且不计次序的意义下，该表示唯一

素数的另一种定义

对整数$p\ne0,\pm1$，若对任意满足$p|a_1a_2$的整数$a_1,a_2$均有$p|a_1$或$p|a_2$成立，则称p是素数

同余

定义

设$m\ne0$。若$m\mid(a-b)$，称m为模数，当 $xm=y m $时，我们说 x 和 y 关于 m 同余，表示为 $x≡y(\bmod m)$，这种表示称为模m的同余式

性质

定理 1 当 \[a \equiv b \pmod m\] 且 \[d \mid m\] 时，有 \[a \equiv b \pmod d.\]

定理 2 当 \[a \equiv b \pmod m\quad\text{且}\quad c \equiv d \pmod m\] 时，有

  a + c \equiv b + d \pmod m,\\
  a - c \equiv b - d \pmod m,\\
  a \times c \equiv b \times d \pmod m.

- **定理 3**  当  $$ac \equiv bd \pmod m\quad\text{且}\quad \gcd(c,m)=1$$  时，有  $$a \equiv b \pmod m.$$
  
- **定理 4**  当  $$a \equiv b \pmod m$$  时，对于任意的 $c\neq0$，有  $$ac \equiv bc \pmod m.$$
  
- **定理 5**  当  $$a \equiv b \pmod m$$  时，对于任意的 $k>0$，有  $$a^k \equiv b^k \pmod m.$$
  
- **定理 6**  当  $$a \equiv b \pmod m$$  时，对于任意的整数 $t$，有  $$a = b + t\,m.$$

## 同余原理

当需要返回数据很大，超过了longlong的范围，一般需要返回一个数字对另一个数字取模的结果

对于四则运算，位数（bits）固定，我们认为时间复杂度为$O(1)$，但保留中间结果的情况下，位数可能会改变，导致复杂度增加

**定理：对于k位（非32、64位）整数，加减的复杂度为$O(k)$，乘除的复杂度变为$O(k^2)$**

此时需要同余原理

同余的数学化表示：

### 加法同余

对于$(a+b)\bmod{k}=c$，为了避免$a+b$得到更大的位数以出现问题，我们可以分别对$a$和$b$取模再相加取模，即$(a\bmod{k}+b\bmod{k})\bmod{k}=c'$，这样可以把$a$和$b$限制在32或64位，结果$c=c'$

### 乘法同余

对于$(a\times b)\bmod{k}=c$，分别对$a$和$b$取模再相乘取模，即$(a\bmod{k}\times b\bmod{k})\bmod{k}=c'$，这样可以把$a$和$b$限制在32或64位，结果$c=c'$

**注意：要保证相乘时中间结果不能溢出**

### 减法同余

关于取模，若一个数取模后的结果是负数，**则需要加一个模数后取模**，以获得他的正数表示

例如一个数%7的结果是-2，等同于这个数+7后%7的结果5，因为两者加2后分别是0和7，都可以被7整除

对于$(a-b)\bmod{k}=c$，我们需要在分别模m的基础上加一个m，即$((a\bmod{k}-b\bmod{k})+m)\bmod{k}=c'$，为了避免获得负数中间结果

# C/C++的整数除法与取模

## 规定

C/C++规定在整数除法中：

- 除数为0时，行为未定义
- 否则$\frac{a}{b}\times b+a\% b=a$

即取模运算的符号取决于除法如何取整，而这是实现定义的

从C++11起，规定**商向零取整**，取模的符号**与被除数相同**

5 % 3 == 2; 5 % -3 == 2; -5 % 3 == -2; -5 % -3 == -2;

## 快速乘

要求模数在long long范围内的乘法取模，避免整数溢出，可以使用快速乘，能够实现$O(1)$且不需要`int128`

我们可以发现：$a\times b\bmod{m}=a\times b-\lfloor\frac{ab}{m}\rfloor\times m$

使用ull的自然溢出，可得：$a\times b\bmod{m}=a\times b-\lfloor\frac{ab}{m}\rfloor\times m=(a\times b-\lfloor\frac{ab}{m}\rfloor\times m)\bmod{2^{64}}$

对于$\lfloor\frac{ab}{m}\rfloor$，若结果r在$[0,m)$时，直接返回r，否则返回$r+m$



```c++
long long binmul(long long a, long long b, long long m) {
  unsigned long long c =
      (unsigned long long)a * b -
      (unsigned long long)((long double)a / m * b + 0.5L) * m;
  if (c < m) return c;
  return c + m;
}

数论函数

数论函数指定义域为正整数的函数，可以视为一个数列

积性函数

定义

数论中，若函数$f(n)$满足$f(1)=1$，且$f(xy)=f(x)f(y)$对任意互质的$x,y\in \N^*$都成立，则$f(n)$为积性函数
数论中，若函数$f(n)$满足$f(1)=1$，且$f(xy)=f(x)f(y)$对任意的$x,y\in \N^*$都成立，则$f(n)$为完全积性函数

性质

若 $f(x)$ 和 $g(x)$ 均为积性函数，则以下函数也为积性函数：

$h(x)=f(x^p)$
$h(x)=f^p(x)$
$h(x)=f(x)\,g(x)$
\[h(x)=\sum_{d\mid x}f(d)\,g\Bigl(\frac{x}{d}\Bigr)\]

对正整数 $x$，设其唯一质因数分解为
\[ x=\prod_i p_i^{k_i}\,, \] 其中 $p_i$ 为质数，$k_i$ 为正整数。

若 $F(x)$ 为积性函数，则
\[ F(x)=\prod_i F\bigl(p_i^{k_i}\bigr)\,. \]
若 $F(x)$ 为完全积性函数，则
$$ F(x)=_i F(p_i^{k_i}) =_i^{k_i},.

$$

加性函数

定义

数论中，若函数$f(n)$满足$f(1)=1$，且$f(xy)=f(x)+f(y)$对任意互质的$x,y\in \N^*$都成立，则$f(n)$为积性函数
数论中，若函数$f(n)$满足$f(1)=1$，且$f(xy)=f(x)+f(y)$对任意的$x,y\in \N^*$都成立，则$f(n)$为完全积性函数

性质

对正整数 $x$，设其唯一质因数分解为
\[ x = \prod_i p_i^{k_i}, \] 其中 $p_i$ 为质数，$k_i$ 为正整数。

若 $F(x)$ 为加性函数，则有
\[ F(x) = \sum_i F\bigl(p_i^{k_i}\bigr)\,. \]
若 $F(x)$ 为完全加性函数，则有
\[ F(x) = \sum_i F\bigl(p_i^{k_i}\bigr) = \sum_i F(p_i)\,\cdot k_i\,. \]

红魔咖啡馆

【数学】数论基础

整除

定义与性质

约数

余数

余数

带余数除法

余数的性质

最大公约数与最小公倍数

最大公约数

定义

性质

求法

欧几里得算法

扩展欧几里得算法

更相减损术

互素

快速GCD

预处理

更相减损术

最小公倍数

定义

性质

求法

素数与合数

算术基本定理

内容

素数的另一种定义

同余

定义

性质

数论函数

积性函数

定义

性质

加性函数

定义

性质