取模優化

就不講怎么減少取模了。

比較廣為流傳的有兩種，Barrett reduction，Montgomery Algorithm。

對于固定常數模數，計算機已經優化的很好了，一般不會有太大效果（確實有，用 Barrett reduction 有時可以卡常）。

對于輸入的固定模數（即不會改變），可以用一下算法優化。

Barrett reduction：

一句話總結，比較有用，比較好寫

考慮對于 \(a\bmod m\)，可以用 \(a-m\lfloor \frac{a}{m}\rfloor\)，但是直接計算 \(\lfloor \frac{a}{m}\rfloor\)，由于除法的常數，并不會快。

眾所周知，不能精確計算的就粗略計算，考慮除以 \(2^k\) 是快的，因為可以用位運算，于是我們考慮將 \(\lfloor \frac{a}{m}\rfloor\) 用除以 \(2^k\) 估算。

具體的，設 \(base=\lfloor \frac{2^k}{m} \rfloor\)，于是 \(\lfloor \frac{a}{m}\rfloor\) 可以粗略計算為 \(\lfloor \frac{base*a}{2^k}\rfloor\)。

優點是簡潔好寫，缺點是有一定錯誤率，且需要用 __int128。

錯誤率：顯然，\(\lfloor \frac{base*a}{2^k}\rfloor \le \lfloor \frac{a}{m} \rfloor\) 對于 \(k\) 取 \(64\) 時，\(m\) 在 \(10^9\) 左右的模數，極限值域在 \(10^{18}\) 時，用 __uint128_t 存儲 \(base\)，在測試了 \(10^{10}\) 組純隨機數據中，\(\lfloor \frac{a}{m} \rfloor - \lfloor \frac{base*a}{2^k}\rfloor \le 1\)，可以加上判斷來減掉誤差（雖然會變慢）。

Montgomery Algorithm：

一句話總結，卵用沒有。

考慮對于加減法，顯然可以用判斷來代替取模，對于乘法（\(ab \bmod m\)），我們考慮優化。

這里我們需要 \(m\perp 2\)。

設 \(R=2^k > m,a'=aR \bmod m,b'=bR \bmod m\)。

顯然有 \(abR \equiv a'b'R^{-1} \pmod m,a'R^{-1}\equiv aR^2 \pmod m,b'R^{-1}\equiv bR^2 \pmod m\)，而 \(R^2 \bmod m\) 是可以預處理的，所以我們只要能夠快速求出 \(xR^{-1}\bmod m\) 就可以快速求出 \(a',b'\)，進而求出 \(abR,ab\)。

如何求出 \(xR^{-1}\) ，考慮求最小的 \(k\) 滿足 \(R | x+km\)，在將 \(R\) 除掉即可，\(k\equiv -xm^{-1} \pmod R\)，提前處理 \(m^{-1} \bmod R\)即可。

優點是不用 __int128，并且實現精細的話可能更快，缺點是必須精細實現，要封裝 \(modint\) 來減少轉換，細節較多（反正我調了一下午還不如本地動態模數暴力快，提交比固定模數略慢）。

唯一的作用沒準就是做模板題 at_arc148_f。

速度測試以后會補，有簡單的本地評價： Barrett reduction 未加判斷。

固定模數： \(默認=Barrett reduction<Montgomery Algorithm\)

非固定數： \(Barrett reduction<默認<Montgomery Algorithm\)

學校 OJ 上固定模數 Montgomery Algorithm 略慢于默認，Barrett reduction 略快于默認。

Barrett reduction，Montgomery Algorithm 都不會受模數是否固定影響。

Upd:
給一個板子：

Mbs = (__int128(1) << 64) / MOD; // init
int Mod(llt x){ return (x -= (x * Mbs >> 64) * MOD) >= MOD ? x - MOD : x; }