998244353這個數字有什麼特殊的性質？

如題

---

FFT做OI題，有的時候是要算一些組合計數啥的，我們就往往對一個數取模；而如果模數為一個質數且為2^k*奇數+1（說白了就是把模數-1分解質因數），我們關注一下2^k這個因子，如果2^k&>2n的話，就可以在模意義下做FFT也就是NTT。

這個科技引入之後，出現了不少題，但是當時有個問題就是一般出題人就會告訴你模數的特點，那選手一下子就知道是NTT了。

然後vfk就表示以後所有取模的題，都對這個數取模，這樣選手就看不出來了。

現在幾年過去了目的基本上就達到了。

所以總之性質就是：

①，質數

②，2^23*7*17+1,2^23一般來說都遠大於題目的n

③，不算太大，模意義做加法用int不會爆

---

它的二進位表達是：111011100000000000000000000001

它是一個質數。

它是一個奇數。

它可以表達為兩個數的平方和：998244353 = 3943^2 + 31348^2

它是勾股數之一：998244353^2 = 247210328^2 + 967149855^2

它可以被表達為：998244353 = 7 * 17 * 2^23 + 1

---

沒看出啥特別的，只是直觀的看到不要998，只要244，還送353元大禮包…

---

中午吃多了(按拼音九宮格打出來的字，這是你要的答案嗎？)

---

998244353=7×17×223+1，一個質數
UOJ專用NTT模數

---

NTT二數之一

但是據我觀察，我和我身邊的同學們一致認為1004535809背的更順口一點。。。

---

要是銀行卡里的就好了

---

推薦閱讀：