标签：信息学 frac gcd ll 奥赛 mod 初等质数 equiv

初等数论

初等数论

整除与约数

带余除法和整除

对于两个整数 $d,a$，存在两个唯一的整数 $q,r$，满足

\[a=qd+r(0\le r < d) \]

则称$q,r$为$a÷d$的商和余数。

质数与约数

对于正整数$d,a$，若$d|a$，则称$d$是$a$的约数。

若$a>2$且除了$a$和$1$以外没有别的约数，则称$a$为质数。

一些事实：

质数有无穷多个；
$π(n)→n/\ln n$（$π(n)$表示$n$以内的质数数量）；
$p_n=\Theta (n \log n)$（$p_i$表示第$i$个质数）；
$\sum^n_{i = 1}\frac{1}{p_i}=\Theta (\log \log n)$（$\sum^n_{i = 1}\frac{1}{i}=\Theta (\log n)$）。

算数基本定理

对于任意整数都有且只有一种质因数分解，表示为

\[a=\prod_{i=1}^{n}p_i^{c_i}(\{p_i:i\in [1,n]\}\subseteq P) \]

公约数和公倍数

公约数：对于正整数$a,b$，若$d|a$且$d|b$，则称$d$是$a,b$的公约数。对于其中最大的$d$，称$d$为$a,b$的最大公约数，记作$\gcd(a,b)=d$。约定$\gcd(0,a)=a$。
公倍数：对于正整数$a,b$，若$a|d$且$b|d$，则称$d$是$a,b$的公倍数。对于其中最小的$d$，称$d$为$a,b$的最小公倍数，记作$\text{lcm}(a,b)=d$。约定$\text{lcm}(0,a)=0$。

唯一分解下：

设

\[a=\prod_{i=1}^{n}p_i^{c_i}, b=\prod_{i=1}^{n}p_i^{c'_i} \]

则根据定义，有

\[\gcd(a,b)=\prod_{i=1}^{n}p_i^{\min\{c_i, c'_i\}}, \text{lcm}(a,b)=\prod_{i=1}^{n}p_i^{\max\{c_i, c'_i\}} \]

性质：

$\gcd(a,b)\text{lcm}(a,b)=ab$；
$\gcd(ac,bc)=\gcd(a,b)·c$；
若$\gcd(a,b)=1$，则$a|c,b|c$，可推出$ab|c$；
若$\gcd(a,b)=1$，则$a|bc$，可推出$a|c$；
若$\gcd(a,b)=1$，则$\gcd(a,bc)=\gcd(a,c)$。

$a$和$b$互质$\Lrarr \gcd(a,b)=1 $。

例题
Luogu P1029 最大公约数和最小公倍数问题（加强）

更相减损术

更相减损术：当$b \leq a$，$\gcd(a,b)=\gcd(a-b,b)$。可以用来求最大公约数，但是复杂度最坏为$O(a)$。

推论：

对任意整数$q$，$\gcd(a,b)=\gcd(a+qb,b)$；
$\gcd(a,b)=\gcd(a \mod b,b)(a \mod b =a-\lfloor a/b\rfloor ·b)$。

欧几里得算法（辗转相除法）

欧几里得算法（辗转相除法）：$\gcd(a,b)=\gcd(b, a\mod b)$。

复杂度为$O(\log\min{\set{a,b}})$。因为当$a\geq b$，$a\mod b<\frac{a}{2}$。

示例代码：

int gcd(int a, int b)
{
  if (!b)
    return a;
  return gcd(b, a % b);
}

裴蜀定理

欧几里得算法中，观察到每一步参数都是$a$和$b$的线性组合。

裴蜀定理：对于任意整数$a,b$，其不全为$0$，有：

$\forall x,y\in \Z$，有$\gcd(a,b)|(ax+by)$；
$\exist x,y\in \Z$，使得$\gcd(a,b)=ax+by$。

推论：

$\gcd(a,b)=1\Leftrightarrow \exist x,y\in \Z$，$gcd(a,b)=ax+by$；
若$ax+by>0$则$ax+by$的最小值为$\gcd(a,b)$。

拓展欧几里得算法（Ex-GCD）

利用求最大公约数的过程，求上述存在的$x,y$。

若$b=0$，则$x=1,y=0$。
否则，令$a'=b,b'=a\mod b$。假设$a'x'+b'y'=\gcd(a,b)$，则$bx'+(a-\lfloor \frac{a}{b}\rfloor)y'=\gcd(a,b)\Leftrightarrow ay'+b(x'-\lfloor\frac{a}{b}\rfloor y')=\gcd(a,b)$。因此令$x=y',y=x'-\lfloor a/b\rfloor y'$即可

\[ax+by=\gcd(a,b)\Rightarrow bx'+(a \mid b)y'=\gcd(a,b):\\ x=y',y=x'-\lfloor \frac{a}{b}\rfloor y' \]

代码模板：

#define ll long long
void extGcd(ll a, ll b, ll &d, ll &x, ll&y)
{
  if (!b)
    d = a, x = 1, y = 0;
  else
  {
    extGcd(b, a % b, d, y, x);
    y -= x * (a / b);
  }
}

算法给出一组解$(x_0, y_0)$之后，当$b≠0$时这个解满足$|x_0|\leq \frac{b}{\gcd(a,b)},|y_0|\leq \frac{a}{\gcd(a,b)}$，所有$(x,y)$为

\[\begin{cases} x = x_0 + k\frac{b}{\gcd(a,b)}\\ y = y_0 - k\frac{a}{\gcd(a,b)} \end{cases} (k\in \Z) \]

例题
Luogu P3951 [NOIP2017 提高组] 小凯的疑惑 / [蓝桥杯 2013 省] 买不到的数目
CF 1427E Xum

同余

若$m|(a-b)$，则$a\equiv b(\mod m)$

性质：

$\equiv$是等价关系
$\forall a, \exist\ 0\leq b < m, a\equiv b(\mod m)$；
$a\equiv b(\mod m)\land d|m, d|a, d|b \Rightarrow \frac{a}{d}\equiv \frac{b}{d} (\mod \frac{m}{d})$
$a\equiv a'(\mod m) \land b\equiv b'(\mod m)\Rightarrow a+b\equiv a'+b'(\mod m)\land ab\equiv a'b'(\mod m)$。

在$\mod m$意义下进行类似除法的操作，定义$x\equiv \frac{d}{a}(\mod m)$，其中$x$满足$ax\equiv d(\mod m)$。

同余方程

\[ax\equiv d(\mod m)\Lrarr ax+my=d \]

用Ex-GCD求出满足$ax'+my'=\gcd(a,m)$的$x',y'$：

若$\gcd(a,m)\nmid d$，则方程无解；
若$gcd(a,m)|d$，则
\[x=\frac{d}{\gcd(a,m)}x',y=\frac{d}{\gcd(a,m)}y' \]
是$ax+my=d$的一组解

例题
Luogu P1082 同余方程

逆元

可以用扩展欧几里得定理计算。

当$d=1$，即$ax\equiv 1(\mod m)$时，称$x$为$a$在模$m$意义下的乘法逆元，记作$x=a^{-1}$

#define ll long long
void extGcd(ll a, ll b, ll &d, ll &x, ll&y)
{
  if (!b)
    d = a, x = 1, y = 0;
  else
  {
    extGcd(b, a % b, d, y, x);
    y -= x * (a / b);
  }
}
ll inv(ll a, ll m)
{
  ll d, x, y;
  extGcd(a, m, d, x, y);
  return (x % m + m) % m;
}

性质：

$a·a^{-1}\equiv 1(\mod m)$
$a^{-1}$存在当且仅当$\gcd(a,m)=1$

特别地，当$m$是质数，对所有$1≤a<m$都有$\gcd(a,m)=1$,所以$a-1$一定存在（除了$0$，就像$0$不能做分母）。因此$a^{-1}$可以看作模意义下的除法运算。

很多涉及到有理数运算的题目都会用输出${\mod p}$的结果替代输出实数值（其中$p$是一个质数），以避免精度问题。

常见的$p$有$998244353$，$10^9+7$等。

预处理逆元

若$p$为质数而且需要多次用比较小的数的逆元，可以递推预处理逆元，每次$O(1)$查询即可。

$1^{-1}=1$；
当$i\geq 2$，因为$p\mod i=p-\lfloor \frac{p}{i}\rfloor ii^{-1}$，两边乘$i^{-1}$和${p\mod i}$，有
\[i^{-1}\equiv -\lfloor \frac{p}{i}\rfloor(p\mod i)^{-1}(\mod p) \]

参考代码：

inv[1] = 0;
for (int i = 2; i <= n; i++)
  inv[i] = (p - p / i) * inv[p % i] % p;

如果预处理阶乘的逆元，用$f_i$存放$i!$，$g_i$存放$(i!)^{-1}$：

先预处理$f_i=i!$，递推
求$g_n=f_n^{-1}$
倒推：因为$g_{i-1}=((i-1)!)^{-1}=i·(i!)^{-1}$，所以$g_{i-1}=i·g_i$

威尔逊定理

$\forall p \in P ,(p-1)!\equiv -1(mod p)$

前置：

$a=a^{-1}$当且仅当$a=1 \lor a=-1$
$(a^{-1})^{-1}$

所以$[2,p-2]$中所有数可以$a$与$a^{-1}$匹配相乘，全部乘起来是$1$，即$(p-2)!\equiv (\mod p)$。

所以$(p-1)!\equiv (p-2)!·(p-1)\equiv -1(\mod p)$

例题
AHOI 2005 洗牌

完全剩余系

模$m$下的完全剩余系：对$m取模后能够恰好取遍$0~m一1$的$m$个数。

性质：在模$m$的完全剩余系中，

对每个数$+a$后还是完全剩余系，即$(i+a)\mod m$取遍$0~m一1$。
若$\gcd(a,m)=1$,则对每个数$×a$后还是完全剩余系，即$(i·a)\mod m$取遍$0~m-1$。

费马小定理

费马小定理：$\forall p \in P , 1\leq a < p, a^{p-1}\equiv 1(\mod p)$

证明：当$i$取遍$1~p-1$时，$ai$也取遍$1~p-1$

所以

\[(p-1)!\equiv Prod^{p-1}_{i=1}i\equiv \]

推论：$a^n\equiv a^{n\mod (p - 1)} (\mod p)$

可用来求乘法逆元。

参考代码：

#define ll long long
ll power(ll a, ll b, ll p)
{
  ll ret = 1;
  for (; b; b>>= 1, a = a * a % p)
    if (b & 1)
      ret = ret * ret % p;
  return ret;
}
ll inv(ll a, ll p)
{
  return power(a, p - 2);
}

Miller-Rabin测试

暴力判质数的复杂度是$O(\sqrt{n})$。

费马小定理：$p$是质数$\Rarr a^{p-1}\mod p=1$。

但是$a^{p-1}\mod p=1\not\Rarr p$是质数

强伪素数：对所有互质的$a$都满足$a^{m-1}\mod m=1$的合数$m$，比如$m=561=3×11×17$。

对于质数$p$，若$x^2\equiv 1(\mod p)$，则$x\equiv\pm 1(\mod p)$。

Miller-Rabin素性测试：求$a^{m-1},a^{(m-1)/2},..,a^{(m-1)/2^k}$，直到$a^{(m-1)/2}\mod p≠1$，判断

这个结果是不是$-1$，如果是$-1$就认为是质数。

只需要选前$9$个质数作为$a$就可以测试$10^{18}$以内的数。

复杂度$O(\log n)$。

简化剩余系

模$m$下的简化剩余系：取遍所有与$m$互质的数，即$Zm=\{x:1≤x<m,gcd(x,m)=1\}$。

对于任意满足$\gcd(a,m)=1$的$a$（即$a∈Z_m$）,若$i$取遍$Z_m$，则$i·a$取遍$Z_m$。

欧拉定理

欧拉定理：$\forall \gcd(a,m)=1. a^{\Phi(m)}\equiv 1(\mod m)$

扩展欧拉定理

扩展欧拉定理：$\forall a,m,n,\Phi(m)\leq n,a^n\equiv a^{(n\mod \Phi(m))+\Phi(m)}(\mod m)$

可用于降次。

欧拉函数

简化剩余系的大小。

性质：

$\Phi(p)=p-1$（$p$与除了倍数以外的所有数都互质）；
若$\gcd(a,b)=1$，那么$\Phi(ab)=\Phi(a)\Phi(b)$；
对于质数$p$，$\Phi(p^e)=(p-1)p^{e-1}$；
$\Phi(n)=n\prod_{p|n\land p\in P}(1-\frac{1}{p})$。

例题：

Luogu P4139 上帝与集合的正确用法

中国剩余定理

中国剩余定理（CRT）：若$m_1,m_2,...,m_k$两两互质，令

$M=\prod_{i=1}^km_i, n_i=\frac{M}{m_i}$
$n_in_i^{-1}\equiv 1(\mod m)$

则$x\equiv a_i(\mod m_i)$的解为$x\equiv \sum^k_{i=1}a_in_in_i^{-1}(\mod m)$

若$m_i$不两两互质，则每次合并两个方程，转化为CRT可以求的问题。这个定理被称为扩展中国剩余定理（Ex-CRT）。

例题：

SDOI 2010 古代猪文

筛法

积性函数

积性函数：若 $f(1) = 1$ 且对任意互质的 $a,b$ 满足$ f(ab) = f(a)f(b)$，则称 $f$ 是积性函数。
完全积性函数：若 $f(1) = 1$ 且对任意 a,b 满足f(ab) = f(a) f(b)，则称 f 是积性函数。

比如欧拉函数、因子个数、除数函数、恒等函数（完全积性函数）。

埃氏筛

给每个没被打标记的数的所有倍数（不包括自己）打标记，那么最后所有没有标记的数就是质数。

vector<int> Eratosthenes(int n)
{
  vector<int> vis(n + 1);
  vector<int> prime;
  for (int i = 2; i <= n; ++i)
  {
    if (vis[i])
      continue;
    prime.push_back(i);
    for (int j = i * 2; j <= n; j += i)
      vis[j] = 1;
  }
  return prime;
}

欧拉筛

欧拉筛（线性筛）：保证每个合数只会被最小质因数筛掉。

vector<int> Euler(int n)
{
  vector<int> vis(n + 1);
  vector<int> prime;
  for (int i = 2; i <= n; ++i)
  {
    if (!vis[i])
      prime.push_back(i);
    for (int p : prime)
    {
      if (i * p > n)
        break;
      vis[i * p] = 1;
      if (i % p == 0)
        break;
    }
  }
  return prime;
}

线性筛可以用来求线性函数。

假设要求积性函数 $f$ 的值，且 $f(p)$和 $f(p^e ) $已知。

访问 $p_i$ 时，$p $一定不超过$ i $的最小质因子，所以可以分两类讨论：

$p∤ i$：此时 $p$ 与 $i $互质，所以 $f(pi) = f(p) f(i)$。
$p|i$：假设 $i = p^ei'(\gcd(p^e,i' ) = 1)$，则 $f(pi) =f(p^e+1) f(i/p^e )$。

例如用线性筛求欧拉函数：

function<vector<int>(int)> Euler = [&](int n) -> vector<int>
{
  vector<int> vis(n + 1);
  vector<int> prime;
  vector<int> f(n + 1);
  vector<int> cnt(n + 1);
  f[1] = 1;
  for (int i = 2; i <= n; ++i)
  {
    if (!vis[i])
    {
      prime.push_back(i);
      f[i] = i - 1;
      cnt[i] = 1;
    }
    for (int p : prime)
    {
      if (i * p > n)
        break;
      vis[i * p] = 1;
      if (i % p != 0)
      {
        cnt[i * p] = 1;
        f[i * p] = f[i] * f[p];
      }
      else
      {
        cnt[i * p] = 1 + cnt[i];
        f[i * p] = f[i] * p;
        break;
      }
    }
  }
  return f;
};

例题：

Luogu P1835 素数密度

Luogu P6528 GCD

标签：信息学,frac,gcd,ll,奥赛,mod,初等,质数,equiv
From： https://www.cnblogs.com/HERITAGE-Official/p/18331028

【信息学奥赛提高组】简单、初等数论