前言
我发现我的数论知识整理 ， 整理的真的很乱，我觉得有必要重新整理梳理一下，就先从同余开始吧，前面的也没有什么可以梳理的，就是比较简单的结论和证明。(但也不代表本章很难，笔者是个 (fw) ，所以整理不出很 (nb) 的东西)
这篇文章能够提供什么学习内容，即这篇文章你能够学到什么 ：
- (1.) 欧拉函数 ( ext{&}) 欧拉定理
- (2.) 乘法逆元
- (3.) 扩展欧几里得
- (4.) 同余方程
- (5.) 中国剩余定理
一些表示
- (1.) (equiv) 表示的模意义下相等
- (2.) (varphi) 表示欧拉函数
- (3.) (p) 无特殊说明为一个质数。
同余的性质
- (1.) 自反性：(a equiv a (mod p ))
- (2.) 对称性：(a equiv b, b equiv a (mod p))
- (3.) 传递性：(aequiv b ,bequiv c , aequiv c(mod p))
- (4.) 满足运算律 (a equiv b , c equiv d , aigoplus c equiv bigoplus d(mod p))
(igoplus) 代表运算。
虽然说很显然，但是也是需要放在前面的。
还有就是，对负数取模的时候， (ret = (ret + mod) ext{%} mod) , 当然，不要 (define int unsigned long long) , 该事例来源于机房某憨批。
欧拉函数 & 欧拉定理
首先声明，欧拉函数是没有欧拉定理的。
欧拉函数
(varphi(N)) 为欧拉函数，为 ([1,N]) 中与 (N) 互质的数的个数。
一个小定理 ：
- (N = prod_{
m{p|N}}{p_i}^{c_i})
(varphi(N) = N imes prod_{p|N}(1 - frac{1}{p}))
证明 ： 涉及一个容斥原理。
我们设 (N) 的一个质因子为 (p) , 那么 (p) 的倍数有 (frac{N}{p}) 个，同理，若 (q) 也是 (N) 的一个质因子，那么 (q) 的倍数有 (frac{N}{q}) 个，
我们去掉这些数 (因为不能有互质的，(N) 和他们的最大公约数都不是，是 (p) 或 (q)) .
那么我们就删掉了 (pq) 的倍数两次，给它加回来（容斥） 。
那么最后我们能得到 (N - frac{N}{p} - frac{N}{q} + frac{N}{pq} = N imes (1 - frac{1}{p}) imes (1 - frac{1}{q}))
如果需要计算欧拉函数的话，我们就根据上述，直接搞一个质因数的分解，顺带求出欧拉函数。
欧拉定理
若正整数 (a , n) 互质，则 (a^{varphi(n)} equiv 1(mod p)) 。
证明 ： 咕了。
欧拉定理的推论
若正整数 (a,n) 互质，则对于任意的正整数 (b) ，有 (a^b equiv a^{b mod varphi(p)} (mod p))
证明：来源：抄书
设 (b = q imes varphi(p) + r) , 其中 $ 0 leq r < varphi(p) $ , 即 (r = b mod varphi(p))
(a^b equiv a^{q imes varphi(p) + r}equiv a^{varphi(p)^q} imes a^r equiv 1^q imes a^r equiv a^r equiv a^{b mod varphi(p)} (mod p))
得证。
扩展欧拉定理
证明 ： 且咕。
乘法逆元
为什么这里要说一下乘法逆元呢？ 首先是这里有时候会
因为在模运算中，是不支持除法的，但是我们可以将 (frac{a}{b}) 转化成 (a imes b^{-1}) 的乘法，那么我们这个时候只需要求解出 (b^{-1}) 就好了，你可能会说，这不就是 (frac{1}{b}) 吗？ 的确，但是你要明白的是，模运算不支持除法。所以，我们求解 (b^{-1}) 就不能直接 (frac{1}{b})
- 事先说明 (b^{-1}) 已经不是 (frac{1}{b}) ，而是代表着 (mod p) 意义下的逆元。
我们继续探寻一下这个逆元的性质 ，也就是 (b imes b^{-1} equiv 1(mod p))
我们探讨一下求解的方法
递推式法
确切地来说，这种方法是最容易理解的一种了。 推点式子嘛。
我们假设 (p = k imes i + r) ， 则显然是有
那么显然我们同样是可以知道的, (k = lfloorfrac{p}{i} floor , r = p ext{%} i)
那么我们显然 (r < i) ，那么我们就有递推式
inv[1] =1 ;
for(qwq int i = 2 ; i <= n ; i++)
inv[i] = (- p / i + p) * f[p % i] ;
费马小定理求解逆元
这里必须保证 (p) 为质数。
证明：咕了。
上文还有一个欧拉定理求解的。
下文还有一个扩展欧几里得求解的。
扩展欧几里得
首先你需要明白什么是欧几里得。
裴蜀定理
对于任意的正整数 (a , b) 若存在正整数 (x ,y) 使得式子 (ax + by = m) , 则 (gcd(a ,b)|m)
证明 ： 我们不断的递归 (gcd(a , b)) ，显然递归到最后一层 ，就是当 (x = 1 , b = 0) 的时候，有一个特殊解 ， 无论 (a) 取什么值，都有 (a imes 1 + 0 imes 0 = gcd(0 , a)) .
然后求解 (gcd) 的过程是递归回溯找到的，那么也就会有 (gcd(b , a ext{%} b) = gcd(a , b)) .现在我们假设存在一组解 (x , y)，使得其一定满足于 (b imes x + (a ext{%}b) imes y = gcd(b , a ext{%} b)) , 则又因为 (a ext{%} b = a - lfloorfrac{a}{b} floor imes b) , 带入式子我们就有[b imes x + (a - lfloorfrac{a}{b} floor imes b) imes y = gcd(a , a ext{%}b) ]这也就等价于
[bx + (a - lfloorfrac{a}{b} floor imes b) imes y <=> ay - b imes (x - lfloorfrac{a}{b} floor) imes y ]然后我们就得到了通解，继续向上不断的寻找，递归到顶部，最后一定能实现，这时候我们不仅证出了结论，亦求解了出来。
- 应用
- (1.) 判断不定方程 (ax + by = m) 是否有解
- (2.) 求解出不定方程 (ax + by = m) 的解。
扩展欧几里得求解逆元
扩展欧几里得求解逆元其实就是对应着求解不定方程对应着 (1) 的情况 。 直接求解即可。 这里给出扩展欧几里得求解不定方程的代码 ：
void exgcd(int a , int b , int &x , int &y) //这里直接传下去，就不用设置全局变量了
{
if(!b) return (void) (x = 1 , y = 0) ;//某人竟然以为会CE
exgcd(b , a % b , x , y) ;
int k = x ; x = y ; y = k - y * (a / b) ;
}
扩展欧几里得求解线性同余方程
我们这货和求解逆元长得很像，其实求解逆元就是这个一个特例。
这个同余方程等价于 (ax + py = c)
然后这货就和不定方程一样了。 直接 (exgcd) 求解即可。
中国剩余定理
又称孙子定理。(什么傻逼名字)
普通中国剩余定理
中国剩余定理也就是让你求解一个线性同余方程组。
即为：
如果 (p_i) 均互质，那么我们称其为中国剩余定理，当然如果不互质，我们叫他扩展中国剩余定理，最后求解出来的是 (x) 的最小值。
- 一些变量设置 ：
- (1.) (M = prod_{i = 1}^{n}p_i)
- (2.) (m_i = frac{M}{p_i})
- (3.) (inv_i) 表示 (m_i) 在 (mod M) 意义下的逆元。
则 (x = sum_{i = 1}^{n} m_i imes inv_i imes a_i)
证明：
证明这东西搞懂搞不懂都行，记住也可以
(emm), 我们直接选择带入反向验证是否是正确的，只要是正确的，那么我最后是 (mod M) 的 ，最小值显然是不必担心的。我们发现 (forall k eq i , a_i imes inv_i imes m_i equiv 0 (mod p_k)) , 带入则显然是成立的。
甚至说，中国剩余定理你都可以不用掌握，直接来到 (excrt) 也是可以的。
void exgcd(int a , int b , int &x , int &y)
{
if(!b) return (void) (x = 1 , y = 0) ;
exgcd(b , a % b , x , y) ;
int k = x ; x = y ; y = k - y * (a / b) ;
}
void init()
{
for(qwq int i = 1 ; i <= n ; i++)
{
a[i] = read() , p[i] = read() ; //剩余 a_i 条猪
M = M * p[i] ;
}
for(qwq int i = 1 ; i <= n ; i++)
{
int mi = M / p[i] ;
exgcd(mi , p[i] , x , y) ;
s = (s + mi * x * a[i]) % M ;
}
}
扩展中国剩余定理
这个时候还是求解线性同余方程组
但是这时候已经不满足 (p_i) 互质了，我们考虑这个问题就只有一个我们是否可以修复呢？很显然答案是否定的。因为在 (p_i) 不互质的情况下， (inv) 可能不存在导致整个算法是错误的。
既然都是合并同余方程组来解决问题的，我们同样也是来合并一下。根据线性同余方程我们可以知道上面的两个式子等价于
我们就知道 (a_1 + p_1k_1 = a_2 + p_2k_2) ， 然后我们继续随便搞一下 (p1k_1 - p_2 k_2 = a_1 - a_2) , 我们发现这个和上述 (ax + by = c) 有着相同的形式，其中 (a_1 , a_2 ,p_1 ,p_2) 均为已知量，在模 (frac{p_1p_2}{gcd(p_1 , p_2)}) 时成立。
然后我们就有了一个 (x = k_1p_1(mod (frac{p_1p_2}{gcd(p_1 , p_2)})))
inline int poow(int a , int b , int mod)
{
int ret = 0 ;
while(b)
{
if(b & 1) ret = ( ret + a ) % mod ;
a = a + a % mod ;
b >>= 1 ;
}
return ret ;
}
inline void exgcd(int a , int b , int &x , int &y)
{
if(!b)
{
x = 1 , y = 0 ;
return ;
}
exgcd(b , a % b , x , y) ;
int k = x ;
x = y ;
y = k - (a / b) * y ;
}
inline int query()
{
int M = a[1] , ans = b[1] , x , y;
for(int i = 2 ; i <= n ; i++)
{
int k = M , l = a[i] , c = (b[i] - ans % l + l) % l ;
int gcd = Base::Gcd(k , l) , lcm = l / gcd ;
exgcd(k , l , x , y) ;
if(c % gcd != 0 ) return -1 ;
x = poow(x , c / gcd , lcm) ;
ans += x * M ;
M *= lcm ;
ans = (ans % M + M) % M ;
}
return (ans % M + M) % M ;
}