取得模 (10^9 + 7) 格式的算術結果
1. 概述
處理大量資料時，中間結果可能會超出資料類型限制。對於這種情況，模組化算術有助於保持數字的可管理性並防止溢位錯誤。
在本教程中，我們將學習如何使用10^9 + 7作為模數的範例格式來執行模算術運算。
2. 基礎知識
在本節中，讓我們回顧一些重要的概念，以幫助我們有效地執行模算術運算。
2.1.對稱模和非負餘數
假設我們要計算a mod b透過應用除法演算法，我們可以得到正餘數（ r ）：
a = qb + r
where, b>0 and r≧0我們必須注意，我們將假設模數 ( b ) 是本文討論範圍內的正數。
隨後，我們可以重寫方程式以獲得負餘數：
a = (q+1)b - (b - r)
where, -(br)≦0從純粹的數學角度來看，這稱為對稱模，其中餘數位於[-b, b)範圍內。然而，當傳回正模數的模運算結果時，大多數程式實現偏好[0, b)範圍內的非負餘數。
2.2.同餘性質
現在，讓我們來看看模算術中處理同餘關係 ( ≡ ) 的另一個有趣的屬性：
(a mod n) = (b mod n) <=> a≡b (mod n)本質上，如果兩個數字a和b除以n時得到相同的餘數，則它們對模n全等。結果，我們可以說10 ≡ 4 (mod 3) 。
2.3.模運算策略
利用對稱模和同餘性質，我們可以透過在可行的情況下在兩個數字中選擇較小的中間結果來制定模算術運算的策略。
為此，我們定義minSymmetricMod()方法，該方法傳回絕對值較小的餘數：
static int minSymmetricMod(int x) {
if (Math.abs(x % MOD) <= Math.abs((MOD - x) % MOD)) {
return x % MOD;
} else {
return -1 * ((MOD - x) % MOD);
}
}作為我們策略的一部分，我們將使用minSymmetricMod()來計算所有中間結果。
此外，讓我們定義保證給出正餘數的mod()方法：
static int mod(int x) {
if (x >= 0) {
return x % MOD;
} else {
return mod(MOD + x);
}
}我們可以使用方法重載來支援long值。
對於我們的用例，我們使用MOD = 10^9 + 7 。然而，除非另有說明，一般原則對於任何其他模值都適用。
我們將把這些概念應用到加法、減法、乘法和其他模算術運算中。
3. 模和
在本節中，我們將學習如何有效地進行模和運算。
3.1.分配財產
模運算遵循加法的分配律：
(a + b) mod n = ((a mod n) + (b mod n)) mod n此外，我們可以對所有中間模運算子使用symmetric_mod ：
(a + b) mod n = ((a symmetric_mod n) + (b symmetric_mod n)) mod n最外面的mod運算保證了正餘數。相反，內部symmetric_mod運算透過適當選擇正餘數或負餘數中的較小者來減少數字的大小。
3.2.計算
我們可以寫modAdd()方法來計算兩個數字的模和：
static int modSum(int a, int b) {
return mod(minSymmetricMod(a) + minSymmetricMod(b));
}現在，讓我們透過計算幾對數字的模和來驗證我們的方法：
assertEquals(1000000006, modSum(500000003, 500000003));
assertEquals(1, modSum(1000000006, 2));
assertEquals(999999999, modSum(999999999, 0));
assertEquals(1000000005, modSum(1000000006, 1000000006));完美的！我們得到了正確的結果。
4.模減法
現在我們已經討論了模加運算，我們可以在本節中將我們的方法擴展到模減法。
4.1.分配財產
讓我們先來看看減法的模運算的分配性質：
(a - b) mod n = ((a mod n) - (b mod n)) mod n此外，讓我們應用**使用symmetric_mod操作來獲得中間結果**的策略：
(a - b) mod n = ((a symmetric_mod n) - (b symmetric_mod n)) mod n就是這樣。我們現在準備好實現這種計算模減法的方法。
4.2.計算
讓我們來寫modSubtract()方法來計算兩個數字的模減：
static int modSubtract(int a, int b) {
return mod(minSymmetricMod(a) - minSymmetricMod(b));
}在底層， minSymmetricMod()確保中間項的大小保持盡可能小。
接下來，我們必須針對不同的數位集測試我們的實作：
assertEquals(0, modSubtract(500000003, 500000003));
assertEquals(1000000005, modSubtract(1, 3));
assertEquals(999999999, modSubtract(999999999, 0));偉大的！結果看起來是正確的。
5. 模乘法
在本節中，我們將學習如何計算兩個數字的模乘。
5.1.分配財產
與加法一樣，模運算也對乘法具有分配性：
(a * b) mod n = ((a mod n) * (b mod n)) mod n因此，我們可以對中間項使用symmetric_mod運算：
(a * b) mod n = ((a symmetric_mod n) * (b symmetric_mod n)) mod n對於所有中間結果，我們將選擇絕對值較低的餘數。最終，我們將**應用mod運算來獲得正餘數**。
5.2.計算
讓我們來寫modMultiply()方法來計算兩個數字的模乘：
static long modMultiply(int a, int b) {
int result = minSymmetricMod((long) minSymmetricMod(a) * (long) minSymmetricMod(b));
return mod(result);
}儘管minSymmetricMod()傳回值的上限為MOD – 1 ，但**相乘後的結果可能會溢出Integer資料類型的限制**。因此，我們必須使用（ long ）類型轉換來進行乘法。
此外，讓我們針對幾對數字測試我們的實作：
assertEquals(1, modMultiply(1000000006, 1000000006));
assertEquals(0, modMultiply(999999999, 0));
assertEquals(1000000006, modMultiply(500000003, 2));
assertEquals(250000002, modMultiply(500000003, 500000003));出色的！看起來我們已經解決了這個問題。
6. 模指數
在本節中，我們將擴展模乘計算方法來計算模冪。
6.1.模指數性質
由於模在乘法上具有分配性，因此我們可以簡化模冪：
(a ^ b) mod n = ((a mod n) ^ b) mod n我們必須注意，模在冪運算上不具有分配性，因為我們沒有對指數b取模。
與之前一樣，我們可以用symmetric_mod運算取代中間項的mod ：
(a ^ b) mod n = ((a symmetric_mod n) ^ b) mod n我們將使用此屬性進行計算。
6.2.計算
讓我們繼續寫一個帶有兩個參數的modPower()方法，即base和exp ：
static int modPower(int base, int exp) {
int result = 1;
int b = base;
while (exp > 0) {
if ((exp & 1) == 1) {
result = minSymmetricMod((long) minSymmetricMod(result) * (long) minSymmetricMod(b));
}
b = minSymmetricMod((long) minSymmetricMod(b) * (long) minSymmetricMod(b));
exp >>= 1;
}
return mod(result);
}我們使用快速冪方法來計算指數值，同時使用minSymmetricMod()計算中間模值。此外，我們進行了（ long)類型轉換來保存乘法結果，該結果可能大於Integer.MAX_VALUE值。
現在，讓我們透過驗證不同的數位對來查看我們的實現：
assertEquals(16, modPower(2, 4));
assertEquals(1, modPower(2, 0));
assertEquals(1000000006, modPower(1000000006, 1));
assertEquals(1000000006, modPower(500000003, 500000003));
assertEquals(500000004, modPower(500000004, 500000004));
assertEquals(250000004, modPower(500000005, 500000005));極好的！我們的方法具有高性能並給出正確的結果。
7.模乘逆
當且僅當a和m互質時a mod m的模乘逆存在**。**對於我們的場景，m= 10^9 + 7是一個質數，它與所有其他數字互質，所以讓我們學習如何找到模乘逆元。
7.1.貝祖特的身份
根據 Bézout 恆等式，我們可以用兩個係數x和y來表示gcd(a, b) ：
gcd(a, b) = x*a + y*b有趣的是，當a和b互質時，我們可以將gcd(a, b)替換為1 ：
x*a + y*b = 1現在，我們對等式兩邊應用mod b運算：
(x*a + y*b) % b = 1 % b
=> (x*a) % b = 1我們已經得到了**模乘逆的定義，即(a -1 * a) % b = 1** 。
求模乘逆元的問題歸結為求 Bézout 係數 ( x )。因此，我們可以使用擴展歐幾裡得演算法來解決我們的用例。
7.2.使用擴展歐幾裡得演算法進行計算
讓我們**來寫一個可傳回最大公約數和 Bézout 係數的extendedGcd()方法**：
static int[] extendedGcd(int a, int b) {
if (b == 0) {
return new int[] { a, 1, 0 };
}
int[] result = extendedGcd(b, a % b);
int gcd = result[0];
int x = result[2];
int y = result[1] - (a / b) * result[2];
return new int[] { gcd, x, y };
}因此，我們現在可以使用extendedGCD()和mod()方法來找到模乘逆：
static int modInverse(int a) {
int[] result = extendedGcd(a, MOD);
int x = result[1];
return mod(x);
}最後，我們必須測試一些數字的實作：
assertEquals(500000004, modInverse(2));
assertEquals(1, modInverse(1));
assertEquals(1000000006, modInverse(1000000006));
assertEquals(1000000005, modInverse(500000003));結果看起來是正確的。
8. 模組化劃分
模乘和模逆是理解模除運算的先決條件。此外，只有當模逆存在時，我們才能進行模除法。
對於兩個互質數a和b ，我們**寫modDivide()方法來計算模除法**：
static int modDivide(int a, int b) {
return mod(modMultiply(a, modInverse(b)));
}如果我們清楚地註意到，它相當於a的模乘和b的模逆。
現在，讓我們來看看一些樣本數字的模除法的實際應用：
assertEquals(500000004, modDivide(1, 2));
assertEquals(2, modDivide(4, 2));
assertEquals(1000000006, modDivide(1000000006, 1));看起來我們已經做對了。
9. 結論
在本文中，**我們**學習了求和、乘法、減法、冪、逆和除法的模算術運算。此外，我們了解到模乘逆運算和除法運算僅適用於互質數。
與往常一樣，本文中的程式碼可以 在 GitHub 上取得。