Mod 取模

tags: Algorithm

定理

• 可以比照等號計算(除了除法,必須除數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次。

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;
}

快速冪取模：

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

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)

a^(m-1) ≡ 1 (mod m)
a^(m-2) ≡ 1/a (mod m)

逆元為 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)

方法二 擴展歐幾裡得算法

擴展歐幾裡得

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

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/10205906?sc=iThelpR
https://blog.csdn.net/acvay/article/details/47397977