# Mod 取模 ###### tags: `Algorithm` ## 定理 ::: info * 可以比照等號計算(除了除法,必須除數k必須和模數m互質,gcd(k,m)=1) * ==重要卻基本 `a ≡ a%m `== a 在除了除法以外 a%m 做其他運算的結果≡ a ::: #### 例題(1) > **15^8001 X 22^4781 X 11^3 除以7的餘數為多少** ``` 15 ≡ 1 (mod 7) 22 ≡ 1 (mod 7) 11 ≡ 4 (mod 7) ``` 1.根據上面==餘的相乘性質的次方公式== ``` 15^8001 ≡ 1^8001 (mod 7) 22^4781 ≡ 1^4781 (mod 7) 11^3 ≡ 4^3 (mod 7) ``` 2.然後上面三條可以相乘 (根據上面==同餘的相乘性質==) ``` 15^8001 X 22^4781 X 11^11 ≡ 1^8001 X 1^4781 X 4^3 (mod 7) 15^8001 X 22^4781 X 11^11 ≡ 64 (mod 7) ``` 然後因為 `64 ≡ 1 (mod 7)` `15^8001 X 22^4781 X 11^3 ≡ 1 (mod 7)` >> **所以餘1** #### 例題(2) >*4793316+7890323 除以7 會餘多少？* 假設我們知道下面 ``` 4793316 ≡ 3 (mod 7) 7890323 ≡ 0 (mod 7) ``` 那根據同餘的加法性質，可以得出 >> 4793316+7890323 ≡ 3(mod 7) ## 取模方式 ### 一般取模運算： >(a^n) %m 我們可以改寫為(a^n)%m= ((a%m)^n)%m,即循環n次。 > 當 a<m(a=a%m) `a^n≡(((((((a)*a)%m)*a)%m)*a)%m` 缺點：低效，循環了n次。 ```cpp= int exp_mod(int a,int n,int m){ a = a%m; int temp = 1; while(n>0) { temp = (temp * a)%m; n--; } return temp; } ``` ### 快速冪取模： ```cpp int qpow( int a, int n, int m) { int res = 1; while (n>0) { if (n&1) res = (res*a)%m; a = (a*a)%m; n>>=1; } return res; } ``` ### 大數 mod ```cpp int bmod( string s, int m) { int res=0; for (int i=0,len=s.size(); i<len; i++) { res=(res*10)%m; res = (res+(s[i]-'0'))%m; } return res%m; } ``` ## 除法 模反元素 a/b 沒辦法變成 (a%m)/(b%m) 但可以將除法轉換成乘反元素,以簡化計算 * 單位元素 可以取消另一元素運算的元素 在mod運算下的單位元素是 1 * 反元素: 跟另一個元素做運算後會等於單位元素的元素 * 模反元素(取模下的乘法反元素 ->除法效果) a*b mod m = 1 * a/b mod m → a*k mod m (k為b的模m乘法逆元) ### 尋找反元素 #### 方法一 費馬小定理 (m為質數且a⊥m) ```cpp a^(m-1) ≡ 1 (mod m) a^(m-2) ≡ 1/a (mod m) ``` ::: info 逆元為 a^(m-2)。（都要求a和m互質） ::: 1. >例 **2^100 mod 13** ``` 2^12≡1 (mod 13) (2^12)^8 ≡ 1^8 (mod 13) (2^12)^8*2^4 ≡ 2^4 (mod 13) 2^100 ≡ 16 (mod 13) 2^100 ≡ 3 (mod 13) ``` #### 方法二 擴展歐幾裡得算法 [擴展歐幾裡得](https://hackmd.io/vWIyTsIVTvSgNGjYDQTEnA#%E6%93%B4%E5%B1%95%E6%AD%90%E5%B9%BE%E8%A3%A1%E5%BE%97%E7%AE%97%E6%B3%95) ``` a * x ≡ 1 (mod n) 若gcd(a,n) = 1 → a*x + n*y = 1+0 = gcd(a,n) = 1 (mod n) → 可以用extgcd()算 → 已知 a,n 求 x,y ``` ```cpp= int exgcd(int a, int b, int &x, int &y) { if(b == 0) { x = 1; // 设置b=0时的特殊解 y = 0; return a; } int ans = exgcd(b, a % b, x, y); int t = x; // 将x2, y2换算成x1, y1 x = y; y = t - a / b * y; return ans; } int invele(int a, int m) { int x, y; exgcd(a, m, x, y); if(m < 0) m = -m; int ans = x % m; if(ans <= 0) ans += m; return ans; } ``` >[https://ithelp.ithome.com.tw/articles/10205727](https://ithelp.ithome.com.tw/articles/10205727) >[https://ithelp.ithome.com.tw/articles/10205906?sc=iThelpR](https://ithelp.ithome.com.tw/articles/10205906?sc=iThelpR) >[https://blog.csdn.net/acvay/article/details/47397977](https://blog.csdn.net/acvay/article/details/47397977)