初等数论

模方程

基础性质

模的等价关系

自反性
$$ a\equiv a \mod m $$
对称性
$$ a\equiv b \mod m\Leftrightarrow b\equiv a \mod m$$

传递性
$$
a\equiv c \mod m, c\equiv b\mod m \Rightarrow a\equiv b \mod m
$$

等式的性质

可加减性
$$
模m意义下\
a\equiv b, c\equiv d \Rightarrow a+c\equiv b+d
$$
可乘性
$$
模m意义下\
a\equiv b, c\equiv d \Rightarrow ac\equiv bd
$$

证明：设$a-b=km$, $c-d=lm$. 则$a=b+km$, $c=d+lm$, $ac=klm^2+(bl+ck)m+bd$, 显然$m|(ac-bd)$

推论：模$m$意义下,$a\equiv b \Rightarrow an\equiv bn$, $n$是自然数

消去律（乘法逆元的充要条件）
$$
模m意义下\
ac\equiv bc, gcd(c,m)=1 \Rightarrow a\equiv b
$$

证明：m|c(a-b), 因为c,m公因子为1，所以m|(a-b).

幂保持恒等
$$
模m意义下\
a\equiv b \Rightarrow a^n\equiv b^n
$$

恒等的最大空间
$$
a\equiv b \mod m_1\
a\equiv b \mod m_2\
\dotsm \
a\equiv b \mod m_n \
\Downarrow \
a\equiv b \mod lcm(m_1, m_2,\dotsm, m_n);
$$

证明：(a-b)是$m_1,m_2,\dotsm,m_n$的倍数，而lcm包含了所有质因子的最大次幂。

推论：若$m_1,m_2,\dotsm,m_n$互质，则$a\equiv b \mod m_1m_2\dotsm m_n;$

换模的另一种途径
$$
a\equiv b \mod c \
\Downarrow \
ad \equiv bd \mod cd
$$

证明：$c|(a-b)\Rightarrow cd|d(a-b)$。

高级定理

贝祖定理

$$
gcd(a,b)是a,b的线性组合。即存在整数x,y,使得xa+yb=gcd(a,b).
$$

证明：

当$a=b$时结论显然成立。

当$a\neq b$时，不妨设$a\neq0$，取$d$为$a,b$的所有线性组合中最小的正整数。作带余除法$a=qd+r$，则$0\leq r<d$. 若$r\neq 0$,则$r=a-qd$是比d更小的线性组合，与假设矛盾,所以$r=0$,$d$是$a$的因子;同理可得$d$是$b$的因子,故$d$是$a,b$的公因子.取$c$为$a,b$的任意公因子,对$d=(xa+yb)$提取$c$得$d=c(xa'+yb')$,可知$c$是$d$的因子,所以$|c|\leq d$,故$d=gcd(a,b)$.

中国剩余定理

$$
有线性同余方程组\
x\equiv a_1 \mod m_1\
x\equiv a_2 \mod m_2\
\dotsm \
x\equiv a_3 \mod m_n \
其中m_i两两互质，则在模M=m_1m_2\dotsm m_n意义下解有且只有一个。\
构造方法如下：
设M_i为\frac{M}{m_i}，在模m_i意义下M_i的逆为t_i。则\
x=\sum_{i=1}^{n} a_it_iM_i
$$

证明：

构造解$x$的正确性。对于方程$i$,$\quad t_iM_i\equiv 1 \mod m_i, M_j\equiv 0 \mod m_i$。所以解满足每一条方程式。

在模$M$意义下解的唯一性。令$x_1,x_2$为方程组的两个不同的解,则$(x_1-x_2)$分别是$m_1,m_2\dotsm m_n$的倍数，则$|(x_1-x_2)|\geq M$，则在模$M$意义下解是唯一的。

欧拉函数

定义

m的化简剩余系（又称既约剩余系，缩系），本文记为$Z_m$
$$
m的剩余系中与m互质的数构成的子集
$$

欧拉函数$\phi(n)$
$$
m的化简剩余系的元素个数，即|Z_m|
$$

性质

1. 对于质数$p$，$\phi(p)=p-1$

2. 对于质数$p$，$\phi(p^k)=p^{k-1}(p-1)$

   证明：在$[1,p^k]$中，不与$p^k$互质的有${p,2p,3p,\dotsc,p^k}$共$\frac{p^k}{p}=p^{k-1}$个数，则互质的有$p^k-p^{k-1}=p^{k-1}(p-1)$个数。

3. 欧拉函数是积性函数，即对于互质的两数$m_1,m_2$，有$\phi(m_1m_2)=\phi(m_1)\phi(m_2)$

证明：设$a\in Z_{m_1}, b\in Z_{m_2}$，则有同余方程组
$$ N \equiv a \mod m_1\
N \equiv b \mod m_2\ $$
其中$a,m_1$互质，$b,m_2$互质，$m_1,m_2$互质。则N在模$m_1m_2$下有且仅有唯一解$N=am_2^{-1}m_2+bm_1^{-1}m_1$，显然$N$与$m_1,m_2$都互质，故与$m_1m_2$互质，$N\in Z_{m_1m_2}$。对任意的$N\in Z_{m_1m_2}$，其对应的$(a,b)$也是唯一的。综上，映射$Z_{m_1m_2}\rightarrow Z_{m_1}\times Z_{m_2}$是满射也是单射，则此映射是双射，故$|Z_{m_1m_2}|=|Z_{m_1}||Z_{m_2}|$，即$\phi(m_1m_2)=\phi(m_1)\phi(m_2)$。

4. 对于质数$p$，且$p|a$，则$\phi(ap)=\phi(a)p$

证明：提取$a$的所有p因子得$ap=a'p^xp=a'p^{x+1}$，由积性函数得
$$ \begin{aligned}
\phi(ap)=&\phi(a')\phi(p^{x+1}) \
=&\phi(a')p^x(p-1)\
=&\phi(a')p^{x-1}(p-1)p\
=&\phi(a')\phi(p^x)p\
=&\phi(a'p^x)p\
=&\phi(a)p
\end{aligned} $$

5. 欧拉函数通项
   $$
   令{p_1,p_2,\dotsc,p_m}为n的所有质因子\
   \phi(n)=n\prod_{i=1}^m(1-\frac{1}{p_i})
   $$

证明：
$$\begin{aligned}
设n=&\prod_{i=1}^mp_i^{x_i}\
由积性&函数得\
\phi(n)=&\prod_{i=1}^{m}\phi(p_i^{x_i})\
=&\prod_{i=1}^{m}p_i^{x_i}(1-\frac{1}{p_i})\
=&n\prod_{i=1}^m(1-\frac{1}{p_i})
\end{aligned}
$$

6. $\phi(n)(n>2)$是偶数

证明：由欧几里得算法可知$\forall i \in [1,n]$且$i$与n互质，则$(n-i)$也与$n$互质。并且$i \neq (n-i)$，这是因为若相等，有$2i=n$，此时$i(i>1)$不与$n$互质。所以与$n$互质的数成对出现，$\phi(n)(n>2)$是偶数。

7. 质因子的次数不超过欧拉函数值
   $$
   设n=p^xs，其中gcd(p,s)=1，则x\leq \phi(n)
   $$

证明：
$$
\begin{aligned}
\phi(n)=&\phi(p^x)\phi(s) \
\geq& \phi(p^x) = p^{x-1}(p-1)
\end{aligned}\
下面证明x\leq p^{x-1}(p-1)
$$
取$p=2$，验证得当$x=1,2,3$时不等式都成立。由归纳法可知$p=2$时不等式成立。取$p>2$，等式左边不变，右边变大，不等式仍成立。

8. $\sum\limits_{d|n}\phi(d) = n$

证明：$\forall k \in [1,n]$，对应有一个$d=gcd(k,n)$。所有可能的$d$取遍了$n$的所有因子。对$d|n$，考虑其对应的$k$，不妨设$k=k_1d,n=k_2d，且gcd(k_1,k_2)=1,那么k_1\leq k_2$。显然$k_2=\frac{n}{d}$是固定的，那么可能的$k_1$的取值有$\phi(k_2)=\phi(\frac{n}{d})$种。所以
$$
n=\sum\limits_{d|n}\phi(\frac{n}{d})=\sum\limits_{d|n}\phi(d)
$$

定理

欧拉定理

$$
对于互质的两个数a,n有\
a^{\phi(n)} \equiv 1 \mod n
$$

证明：设$Z_n={x_1,x_2,\dotsc,x_{\phi(n)}}$，因$a,n互质$，则$ax_i \mod n \in Z_n$；而对$x_i\neq x_j$，由消去律有$ax_i\neq ax_j \mod n$。故模n意义下$Z_n={ax_1,ax_2,\dotsc,ax_{\phi(n)}}$。

故
$$
\prod_{i=1}^{\phi(n)}x_i \equiv \prod_{i=1}^{\phi(n)}ax_i \mod n\
$$
由消去律得
$$
a^{\phi(n)} \equiv 1 \mod n
$$

推论：费马小定理。

扩展欧拉定理（欧拉降幂）

$$
模m意义下\
a^c\equiv
\begin{cases}
a^{c \mod \phi(m)}, \qquad &a,m互质\
a^c, \qquad &a,m不互质，c<\phi(m)\
a^{c \mod \phi(m)+\phi(m)}, \qquad &a,m不互质，c\geq \phi(m)
\end{cases}
$$

证明：$当a,m互质时$，由欧拉定理知$a^{\phi(m)}\equiv 1 \mod m$，定理显然成立。

$当a,m不互质，c<\phi(m)时$，定理显然成立。

$当 a,m不互质，c\geq \phi(m)时$，取$a$的任意质因子$p$，即$a=p^xs且gcd(p,s)=1$，由欧拉定理知
$$p^{\phi(s)}\equiv 1 \mod s$$
由积性函数知$\phi(s)|\phi(m)$，故
$$p^{\phi(m)}\equiv 1 \mod s$$
同余方程同乘$p^x$(换模的另一种途径)得
$$
p^{\phi(m)+x} \equiv p^x \mod m
$$
由欧拉函数的性质7知$x\leq \phi(m)$，已知$\phi(m)\leq c$，所以
$$
x \leq \phi(m) \leq c\
p^c\equiv p^{x+(c-x)}\equiv p^{\phi(m)+x+(c-x)}\equiv p^{\phi(m)+c} \mod m
$$
由$c(c\geq \phi(m))$的任意性和数学归纳法得
$$
p^c\equiv p^{c \mod \phi(m) + \phi(m)} \mod m \
$$
对$p$的幂$p^k$，易得
$$
(p^k)^c\equiv p^{kc}\equiv p^{kc \mod \phi(m)+\phi(m)}\
\equiv p^{kc\mod \phi(m)+k\phi(m)}\equiv (p^k)^{c \mod \phi(m)+\phi(m)} \mod m
$$
对$a=\prod\limits_{i=1}^np_i^{x_i}$，得
$$ \begin{aligned}
a^c\equiv & \prod\limits_{i=1}^n(p_i^{x_i})^c \
\equiv & \prod\limits_{i=1}^n(p_i^{x_i})^{c \mod \phi(m)+\phi(m)} \
\equiv & a^{c \mod \phi(m) + \phi(m)} \mod m
\end{aligned}
$$

---

算法

线性筛质数

求$[1,n]$内的所有素数。

1. 算法核心是每个合数只被其最小质因子筛到。
2. 当前判断完$i$是否质数。接下来筛去i的倍数。枚举已知质数$p_j$，筛去$p_j*i$。若$p_j$是$i$的最小质因子则break。这是因为i以后筛的数都以$p_j$为最小质因子，这些数肯定能被其他的$i$枚举$p_j$筛去，不必重复筛。

   void getPrime(int n) {
       // memset(vis, 0, sizeof(vis));
       pcnt = 0;
       vis[0] = vis[1] = true;
       for (int i=2; i<=n; ++i) {
           if (!vis[i]) prime[pcnt++] = i;
           for (int j=0; j<pcnt && prime[j]*i<=n; ++j) {
               vis[prime[j]*i] = true;
               if (i % prime[j] == 0) break;
           }
       }
   }

线性筛欧拉函数

求$[1,n]$内所有欧拉函数值

1. 算法核心是积性函数和欧拉函数性质4
2. 在线性筛的同时完成欧拉函数计算。当前判断完$i$是否质数，若是合数，则函数值在前面计算过了；若是质数，直接赋值$\phi(i)=i-1$。枚举已知质数$p_j$时，若$p_j$不是$i$的因子，由积性函数可知$\phi(i\cdot p_j)=\phi(i)\cdot \phi(p_j)=\phi(i)\cdot (p_j-1)$ ; 若$p_j$是$i$的因子，由性质4得$\phi(i\cdot p_j)=\phi(i)\cdot p_j$，然后break。

   void getPhi(int n) {
       // memset(phi, 0, sizeof(phi));
       pcnt = 0;
       phi[1] = 1;
       for (int i=2; i<=n; ++i) {
           if (phi[i] == 0) {
               prime[pcnt++] = i;
               phi[i] = i - 1;
           }
           for (int j=0; j<pcnt && i*prime[j]<=n; ++j) {
               if (i % prime[j] == 0) {
                   phi[i * prime[j]] = phi[i] * prime[j];
                   break;
               } else {
                   phi[i * prime[j]] = phi[i] * (prime[j]-1);
               }
           }
       }
   }

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

求$gcd(a,b)$。

1. $gcd(a, 0)$的结果显然等于$a$。
2. 当$a，b$全不为零，则$gcd(a,b) = gcd(b, a \mod b )$使问题规模减小。

   证明：令$c=a\mod b$,则$a=kb+c$.设$r$是$a,b$的公约数，则$r|a-kb$即$r|c$.设$r$是$b,c$的公约数,则$r|kb+c$即$r|a$.可见$a,b$的公约数和$b,a\mod b$的公约数完全相同，则最大公约数也必然相同。

   应用：从$1$到$n(n>2)$中与$n$互质的数成对出现，每一对和为$n$

扩展欧几里得算法

求$ax+by=gcd(a,b)$的一组整数解$x,y$。

1. 直接由贝祖定理可知整数解一定存在。（贝祖定理：存在整数$s，t$使得$sa+tb=gcd(a,b)$）
2. 由辗转相除法知$bx'+(a%b)y'=gcd(b,a%b)=gcd(a,b)$的解也存在。由整数除法得
   $$\begin{aligned}
   bx'+(a%b)y'=&bx'+(a-\frac{a}{b}b)y'\
   =&b(x'-\frac{a}{b}y')+ay'=gcd(a,b)
   \end{aligned}
   $$
3. 递归进行求解，直到$b=0$，显然有解$1a+0b=gcd(a,b)$，令$x=1, y=0$，回溯，得解$x=y', y=x'-\frac{a}{b}y'$
4. 实际写代码时用引用，减少临时变量。

   void exgcd(int a, int b, int &d, int &x, int &y) {
       if (b == 0) {
           x = 1; y = 0;
           d = a;
           return;
       }
       exgcd(b, a%b, d, y, x); // x和y完成了交换
       y -= a / b * x;
   }

类欧几里得算法

求等差数列对每一项做整数除法的和，即
$$
lgcd(a, b, c, n) = \sum_{i=0}^{n-1}\lfloor \frac{ai+b}{c}\rfloor
$$

1. 首先标准化$a,b$，使满足$a\geq 0, b\geq 0$，在答案中预先减去补上的$c$即可。

2. 把$a,b$中含$c$的贡献拆出来，使问题规模变小。答案加上$n\lfloor \frac{b}{c}\rfloor + \frac{(n-1)n}{2}\lfloor \frac{a}{c}\rfloor$。即
   $$
   \sum_{i=0}^{n-1}\lfloor \frac{ai+b}{c}\rfloor = \sum_{i=0}^{n-1}\lfloor \frac{(a%c)i+(b%c)}{c}\rfloor + n\lfloor \frac{b}{c}\rfloor + \frac{(n-1)n}{2}\lfloor \frac{a}{c}\rfloor
   $$
   现在可以令$a'=a%c,\quad b'=b%c$。

3. 计算$\sum\limits_{i=0}^{n-1}\lfloor \frac{a'i+b'}{c}\rfloor$，得到的商肯定介于$[0,\lfloor\frac{a'(n-1)+b'}{c}\rfloor]$，设某次除法得到的商是$x$，可以认为$[1,x]$中每一个数对答案贡献了$1$，考虑每个数的总贡献，则
   $$
   \sum\limits_{i=0}^{n-1}\lfloor \frac{a'i+b'}{c}\rfloor = \sum_{j=1}^{\lfloor\frac{a'(n-1)+b'}{c}\rfloor} \sum_{i=0}^{n-1} [\lfloor \frac{a'i+b'}{c}\rfloor \geq j]
   $$

4. 接下来变换不等式$\lfloor \frac{a'i+b'}{c}\rfloor \geq j$。 取整符号不影响大于等于号的判断，可直接去掉；可直接通分；移项得$a'i\geq jc-b'$。整数除法的同除会影响大于等于号的判断，但不影响大于号，于是右边减一，两边同除$a'$得$i>\frac{jc-b'-1}{a'}$。

5. 为了方便统计合法的$i$，也为了转化形式满足递归，利用补集统计数量。对于固定的$j$，
   $$ \begin{aligned}
   \sum\limits_{i=0}^{n-1} [i>\frac{jc-b'-1}{a'}] =& n-\sum\limits_{i=0}^{n-1} [i\leq\frac{jc-b'-1}{a'}] \
   =& n-(\lfloor\frac{jc-b'-1}{a'}\rfloor+1)
   \end{aligned}
   $$

6. 套上前一层Sigma，得到递归形式（注意j变成从0开始）
   $$
   令m={\lfloor\frac{a'(n-1)+b'}{c}\rfloor} \
   \sum_{j=0}^{m-1}[n-(\lfloor\frac{(j+1)c-b'-1}{a'}\rfloor+1)] = (n-1)m-lgcd(c, c-b'-1,a',m)
   $$

模板

// Sum{(ai+b)/c} for i=0..n-1
LL lgcd(int a, int b, int c, LL n) {
	if (n == 0 || c == 0) return 0;
	LL res = n*(b/c) + (n-1)*n/2*(a/c);
	a = a % c; b = b % c;
	LL m = (a*(n-1)+b)/c;
	return (n-1)*m - lgcd(c, c-b-1, a, m) + res;
}

杂项

注意事项

1. 质因数分解时，质因数要么小于等于$\sqrt{n}$，要么等于$n$。不要漏掉等于$n$的情况。
2. 1e8+7以内的质数
   有5761456个，约为6e6，约为范围的1/15。
   范围越大，质数的占比越小