大杂烩（同余，欧拉，模运算）

几何微粒子 · 2023-02-27 23:07:43 · 个人记录

前言

集训笔只因

Chapter I 同余

设 a = pm + r , b = qm + r ，则 a 同余于 b ，记作 a \equiv b \pmod{m}

同余定理：

若 a \equiv b ，则

a \pm k \equiv b \pm k \pmod{m} $ 范围：$ k \in N
a k \equiv b k \pmod{m} $ 范围：$ k \in N^+
a^k \equiv b^k \pmod{m} $ 范围：$ k \in N^+
同余的性质
自反性，对称性，传递性

满足自反性，对称性，传递性，三种性质的关系，为等价关系。

根据等价关系，可以把目标集合划分为若干个等价类。

剩余类和剩余系

对于模数 m ，利用同余关系（即 n=mk+r 中的余数 r ）可以把整数集合 Z 划分为 m 个等价类，称作模 m 的剩余类，记作

[0],[1],\dots [m-1]

每类各取一个代表元构成的集合称为模 m 的剩余系，一般取

Z_m = {0,1,\dots,m-1}

简化剩余系

对模数 m ，在剩余类 Z_m 中取出与 m 互质的数构成的集合，称为模 m 的简化（既约）剩余系，记作 Z_m^*

显然 Z_m^*| = \varphi_m，因此 Z_m^* 有时也叫做 \phi_m

这里有一个~~玄学的~~表达方式：\{x |\equiv k\pmod{m},k \in \{1,2,\dots,m-1\}\& (k,m)=1\}，意思是当 k \in \{1,2,\dots,m-1\} 且 (k,m)=1 时，有 x |\equiv k\pmod{m}

再探欧拉函数

定义：\varphi_n 为 \le n 且与 n 互质的正整数的个数

有必要写出式子了：

\varphi_n = n\times (1-\dfrac{1}{p_1}) \times (1-\dfrac{1}{p_2}) \times \dots \times (1-\dfrac{1}{p_k})

欧拉函数的重要玄学性质：

欧拉函数是个积性函数：\varphi_n = \prod\limits_{i=1}^{k}\varphi(p_i^{r_i})
其中 \varphi_{p^k} = p^k - p^{k-1}
其他性质还有：
\varphi_n(n>2)$ 的所有元素之和为 $\dfrac{n\varphi_n}{2}
n = \sum\limits_{d|n} \varphi_d

人类智慧思考题：运用欧拉函数，证明质数有无穷个

Chapter II 模运算

OI中常用的模运算，将运算对象集从整数集(Z)缩减到了模 m 的剩余系 Z_m = {0,1,\dots,m-1}

将无限转变为有限
方便存储，运算，输出，验证
通过循环~~彰显人类智慧~~

经典防负数化模运算：

（这里使用了 \% 而非 \mod {} 是为了避免式子又臭又长）

加法：

(a+b)\% m =(a \% m + b \% m) \% m

减法：

(a-b)\%m = (a \% m - b \% m + m ) \% m

乘法：

a\times b \% m = (a \% m) \times (b \% m) \% m

加减法的取模非常的慢，尽量少在加减中用%运算。虽然优化比较简单，但是在该用的时候也不可避免。

小震不用逃，大震逃不了

所以对于上述相对于乘法而言，可以看淡点（但是还是要重视）。

——而乘法则可能会溢出。(a \% m) \times (b \% m) 也可能会爆掉存储范围。

需要一些方法使得在运算乘法的时候不溢出

方法1

快速幂打临时工：~~仍然快速~~龟速乘法

利用性质：

快速幂模板改造

流程：

快速幂模板改造

时间复杂度：0(\log n)

适用范围：

用一些玄学乘法也不行的时候
急需数据稳定性

优点：

时、空、数据稳定性极强
真正意义上的万能模乘

缺点：

慢就是慢，时间稳在非常慢的地步。
容易敲错模板(ans的初始值为0不是1)

方法2

神秘乘法：

利用性质：

一个没有学过的高级知识点——MSK

流程：

int mulmod(int x,int y,int m){
    static const int BLEN=20,BMSK=(1<<20)-1;
    int yH=y>>BLEN,yL=y&BMSK;
    int ret=yH?((x*yH%m)<<BLEN)%m:0;
    return (ret+x*yL)%m;
}

其中的int可以换成各个类型的变量。

适用范围：

m \le {LONG\_MAX^{\frac{2}{3}}}

时间复杂度：O(1)

优点：

复杂度感人（是真的感人！）

缺点：

方法3

玄学乘法

利用性质：

LONG_{MAX} = 9223372036854775807
LONG_{MIN} = -9223372036854775808

流程：

#define LL long long 
LL mulmod(LL x,LL y,LL p){
    LL ret=x*y-(LL)((long double) x*y/m + 1e-8)*m;
    return ret<0?ret+m:retl
}

把数据压入long double中
然后~~玄学算~~
会溢出，但是溢出只会兜几圈，然后溢出之后的数据刚好等于正确答案
只能是long long类型！！！否则溢出的时候就逝世不好说了

适用范围：

时间复杂度：同样是~~真正感人的~~ O(1)

优点：

适用范围广，不怕数据大，~~玄学溢出会给出答案~~

缺点：

只能使用 long long 变量类型

方法4

__int128

优点：

同样无脑
时间复杂度居然也是O(1)

缺点：

手写快读快输才能输入输出
两个long long的内存，当#define int __int128的时候需要注意MLE事故
常数有可能免费大

乘法讲完了，那么除法呢？

b|a$ 时，如何计算 $\dfrac{a}{b}\mod m

**方法1** ~~人类智慧~~公式： $$\dfrac{a}{b}\mod p = \dfrac{a\mod (b\times p)}{b}\mod p$$ ~~啊哈哈哈哈，证明略咯！~~ 适用范围：$b,m$ 互质与否都行 **方法2** 在下面：乘法逆元 --- ### Chapter III 乘法逆元如果存在 $a^{-1}$ 满足 $a\times a^{-1} \equiv 1\pmod m$，则称 $a^{-1}$ 为 $a$ 模 $m$ 意义下的逆元有了逆元便能转除法为乘法。 $\dfrac{a}{b}\mod m = (a\times b^{-1}) \mod m

乘法逆元存在条件：(a,m)=1

乘法逆元的常用求法：

1 费马-欧拉定理 + 快速幂
- a^{-1}\times b \equiv a^{m-2}\times b\pmod{m}
2 exgcd求逆元
- 板子：Chapter IV 第二个
3 线性求逆
- 板子：Chapter IV 第一个

费马-欧拉定理

（又称欧拉定理）

众所周知，费马小定理为

a^{p-1}\equiv 1\pmod m

~~用决心提取机提取费马的灵魂，再让欧拉吸收这个灵魂，让他再次发现费马小定理~~，得到

{\mathsf{\color{black}\colorbox{white}{如果正整数 a,m 互质，则}}}

a^{\varphi_m}\equiv 1\pmod m

由这个定理可以得到

a^{-1} = a^{p-2}$（求逆元方法1的原理）或者 $a^{-1} = a^{\varphi_m-1}

证明费马欧拉定理略。

费马小定理的另外一种形式：a^p\equiv a\pmod{p}

优势是不需要 a,p 互质，只需要 p 为质数即可。

Chapter IV 幂塔

当 b\ge \varphi_m 时

a^b \equiv a^{b\mod \varphi_m + \varphi_m}\mod m

一个更加lip的定理

如果我们设

\varphi_{\varphi_{\dots_{\varphi_n}}}

（套 n 个 \varphi 的~~恶俗玄学~~欧拉函数）

为 {\varphi^k}_p ，则 {\varphi^k}_p 为

\begin{cases}\varphi_{{\varphi^{k-1}}_p}&k>1\\\varphi_p&k=1\end{cases}

则当 k\ge 2\log_2 p 时，{\varphi^k}_p = 1