--- 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)!}$ :::