前言

寫這篇文章的時候，本蒟蒻正在挑戰3個月達省一；
之前一直對模運算耿耿于懷十分好奇，遂決定，今天拿下；
最后在正文開始之前放一個搞笑的東西：

關于模運算的定義

我們先定義帶余除法（其實就是除法）：
\(設兩個數 a,m \in \symbb{Z}, m \not= 0,則a、m的帶余除法定義為：\)
存在唯一的整數q、r（r必須大于等于0），使得

我們記a模m為： \(a \bmod m\)
我們把 \(q\) 稱做商，\(r\) 稱做余數（也稱a模m的結果），記作：

關于114514 & 998244353

在 OI 中，模運算最直接的用處就是解決一些需要處理帶模運算的題目；
而 \(114514\) 和 \(998244353\) 這兩個神奇的模數就不得不提一下了：

\(114514\) 請自行百度（主要是我也沒查出來什么）， \(998244353\) 有如下的幾個特點：
1.它的二進制表達是：111011100000000000000000000001
2.它是一個質數。
3.它是一個奇數。
4.它可以表達為兩個數的平方和：\(998244353 = 3943^2 + 31348^2\)
5.它是勾股數之一：\(998244353^2 = 247210328^2 + 967149855^2\)
6.它可以被表達為：\(998244353 = 7 \times 17 \times 2^{23} + 1\)
7.998244353最優美的性質莫過于它是個完美惡臭數：

之所以稱為完美，因為每一個括號里114514都出現了正整數次；

Tips ：\(998244353\) 最大的一個特點是：出題人 \(99\%\) 的情況下是不會使用這個數的，取而代之的是 \(998234353\) 、\(998244553\) ，不過應該沒人會栽在上面

模運算的兩個等式

這兩個是經常會用到的等式，大部分的OI題目都要求取模
但是通常情況下，這時的結果都遠遠超出了int型的范圍，我們需要在運算過程中就直接取模，而這步的正確性就是依賴于上面的兩個等式

下面我們來證明一下：

證明1:
依據帶余除法，我們設 \(a = q_1m + r_1,\) \(b = q_2m + r_2\)，那么帶入等式左邊，我們有：

更進一步，合并同類項：

引入一個定理：

\(a \bmod m\) 的結果與 \((a+k \times m) \bmod m\) 是一樣的，通俗來說，就是一個數除以另一個數的余數，與這個數加上任意倍的除數之后除以除數的余數是一樣的

顯然，這里相當于有一個商為 \((q_1+q_2)\) ,余數為 \(r_1+r_2\) 的數模 \(m\),當然就等于直接對 \(r_1+r_2\) 模 \(m\) （不妨自己試一下，\(9 \bmod 2\) 和 \(1 \bmod 2\)一不一樣）
所以我們有：

而 \(r_1,r_2\) 就是 \(a \bmod m\) ,\(b \bmod m\) ,帶入得：

證畢

證明2:
仍然依據帶余除法，我們設 \(a = q_1m + r_1,\) \(b = q_2m + r_2\)，那么帶入等式左邊，我們有：

展開：

這里括號內的前兩項仍然是 \(m\) 的倍數，所以可以和1一樣進行替換

而 \(r_1\) 、\(r_2\) 分別是 \(a \bmod m\) ,\(b \bmod m\) ,帶入得：

證畢

同余

如果在計算過程中出現了負數，應該如何處理呢(也就是對負數取模，這里不能直接取，這樣是負的)？
我們回歸問題的本質：求出這個負數除以m的余數

也就是說，我們只要找到一個和這個負數除以m的余數一樣的正數，就可以找到這個負數除以m的余數，而所謂的“和這個負數除以m的余數一樣的正數”，簡稱和這個負數同余（具有同樣的余數）

當然，僅說同余是沒有意義的，我們需要指定模數（除數），才是有意義的；

具體而言：假如有兩個整數 \(x,y\) ，若 \((x-y) \bmod m = 0\) ,則稱 \(x,y\) 在模 \(m\) 意義下同余（具有同樣的余數）

為什么差是倍數就同余呢，仍然依據帶余除法，我們設 \(x = q_1m + r_1,\) \(y = q_2m + r_2\)，那么帶入等式左邊，我們有：

而因為這玩意為0，所以 \((q_1-q_2)m+(r_1-r_2)\) 必然是 \(m\) 的倍數，也就是能寫成 \(n \times m\)的形式（ \(n\) 是一個整數），顯然，\(n = q_1-q_2\) ,所以 \(r_1 - r_2 = 0\)，也就是說，\(r_1 = r_2\) ，即 \(x,y\) 同余;

現在給出定義：對于任意的兩個數 \(x,y\) ，若有 \((x-y) \bmod m = 0\) ,那么我們稱 \(x,y\) 在模 \(m\) 意義下同余，記為：

那么回到最初的問題：如何找到和這個負數同余的正數；
我們假設這個數是 \(-15\)，根據同余的定義，我們有：\(-15 \equiv 5 \pmod{10}\) (\(-15-5 = -20 \bmod 10 = 0\) ，顯然-20是10的-2倍)

那么怎樣從 \(-15\) 推出 \(5\) 來呢？
我們使用 「模m加m」 的方法，即先模m得到一個負數，隨后加上m，就得到了和m同余的正數：
\(-15 \bmod 10 = -5\)，\(-5+10 = 5\),這樣就得到了5，隨后再對5模10即可（這里的負余數-5是大部分的編程語言的默認做法，但是不符合數學定義）；

對于對一個不知正負的數字 \(x\) 取模，我們進行如下計算：
\(x \bmod m = (x \bmod m + m) \bmod m\)

最后

到這里這篇介紹模運算的文章就結束了（當然不包含對除法的取模，這個比較復雜，需要適當了解群論和乘法逆元），可能會有筆誤，歡迎各位指正