---
tags: 數學
title: 模運算1
---
:::info
### 題目放這裡:
- [練習題1--費瑪小定理](https://cses.fi/problemset/task/1712)
- [練習題2--模逆元](https://cses.fi/problemset/task/1079)
- [練習題3--中國剩餘定理](https://atcoder.jp/contests/abc193/tasks/abc193_e)
:::
:::success
## 費瑪小定理
- 設$p$是個質數,$a$是正整數,則
- $a^p ≡ a$ (mod $p$)
- 證明:參考維基百科的證明:
- [連結](https://zh.wikipedia.org/wiki/%E8%B4%B9%E9%A9%AC%E5%B0%8F%E5%AE%9A%E7%90%86)
:::
:::success
## 裴蜀等式
- 設a,b為整數,則對於方程式
- $a\times x + b\times y = gcd(a,b)$
- 必有整數解喔!
- **那要如何快速求x,y呢?**
- 還記得我們怎麼求gcd嗎?輾轉相除大法!
- 如果
- $a\times x_1 + b\times y_1 = gcd(a,b)$
- 有整數解,那麼
- $b\times x_2 + (a\%b)\times y_2 = gcd(a,b)$
- 也有整數解~
- 我們不喜歡 mod 的存在,所以換掉!
- $b\times x_2 + (a-\lfloor \frac{a}{b} \rfloor \times b)\times y_2 = gcd(a,b)$
- 然後整理一下
- $a\times y_2 + b\times(x_2-\lfloor \frac{a}{b} \rfloor \times y_2) = gcd(a,b)$
- 得到遞迴式:
- $x_1 = y_2$
- $y_1 = x_2-\lfloor \frac{a}{b} \rfloor \times y_2$
- 所以我們做輾轉相除法遞迴下去求x,y就好啦~
- 當然,在最後 $a = gcd(a,b)$ 且 $b = 0$ 時,$x = 1, y = 任意數$ 使得等式成立喔~
- 複雜度:$O(log(min(a,b)))$
```cpp=
void extgcd(int a, int b, int &x1, int &y1){
if(b == 0){
x1 = 1;
y1 = 0;
}else{
int x2,y2;
extgcd(b, a%b, x2, y2);
x1 = y2;
y1 = x2 - a / b * y2;
}
}
```
:::
:::success
## 模逆元
- Q:模運算我有加減乘的,有沒有除法的??
- Q:我要電腦算 $C_{2000}^{100000}$ mod $10^9+7$ ,但是不知道怎麼邊算邊取模
- A:因為有除法的關係,取模的部份比較特別~
- 假如我們要計算 $x^{-1}\times y$ (mod $M$),且$M$為質數
- 我們希望找到一個整數$a$,使得 $a\times x ≡ 1$ (mod $M$)
- 如此一來:
- $x^{-1}\times y$ (mod $M$)
= $a\times y$ (mod $M$)
- 所以我們只要找到整數a,便能解決這問題
- 我們不喜歡 mod 的存在,所以在假設一個整數$b$!
- $a\times x + b\times M = 1$
- 因為$M$是質數,$gcd(x, M) = 1$,所以套入裴蜀等式就好啦!
- BTW,我們稱呼 $a$ 是 $x$ 對模數 $M$ 的模逆元
- 複雜度:$O(log(min(a,b)))$
:::
:::success
## 中國剩餘定理
- 韓信點兵問題
- 原問題:$n$ 個人,$n\%3=2$,$n\%5=3$,$n\%7=2$,問 $n$ 最小正整數?
- 方法一(牛頓插值法):
- 令 $n = a\cdot3\cdot5\cdot7+b\cdot3\cdot5+c\cdot3+d$
- $d=2, c=2, b=1, a=$任意整數
- 方法二(使用裴蜀定理):
- 先合併前兩項,令 $m = a\cdot3+2 = b\cdot5+3$
- 解$a\cdot3+b\cdot(-5)=1$,得 $a = 2, b = 1, m = 8$
- 現在的問題變成 $n\%15=8$,$n\%7=2$
- 再合併後兩項,令 $n = a\cdot15+8 = b\cdot7+2$
- 解$a\cdot15+b\cdot(-7)=-6$,得 $a = 1, b = 3, n = 23$
- 得到答案 $n = 23$
:::
:::info
### 補--二項式定理
$(x+y)^n = C_{0}^{n}x^0y^n + C_{1}^{n}x^1y^{n-1}+C_{2}^{n}x^2y^{n-2}+...+C_{n}^{n}x^ny^0$
$C_{k}^{n} = \frac{n!}{k!(n-k)!}$
:::