Barrett 约减优化整数除法/取模
取变量的模其实是非常慢的，而 Barrett 可以在一定情况下将取模化为两次乘法、一次右移以及至多两次减法。
令模数为 $p$。
容易发现：
\[x\bmod p=x-p\left\lfloor\dfrac xp\right\rfloor\]考虑快速求出 $\left\lfloor\dfrac xp\right\rfloor$。
Barrett 选取了 $m,k$，使得：
\[m=\left\lfloor\dfrac{2^k}{p}\right\rfloor\]因此有：
\[\dfrac xp\approx\dfrac{mx}{2^k}\]-
取 $2^k>x(p-1)$ 时可以精确计算。
-
取 $2^k>x$ 时可以保证 $\left\lfloor\dfrac xp\right\rfloor$ 的误差为 $0$ 或 $1$。
因此计算出来的 $x-p\cdot\dfrac{mx}{2^k}$ 的取值范围为 $[0,2p)$。特判即可。
代码实现
一般去 $m=\dfrac{2^{64}}{p}$，可以处理 $\left[-2^{63},2^{63}\right)$ 范围内的整数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
typedef long long ll;
typedef __int128 lll;
struct Barrett{
ll p,m;
inline void build(int P){
p=P;
m=((lll)1<<64)/p;
}
inline ll operator ()(ll x){
ll ans=x-((lll)x*m>>64)*p;
if(ans>=p){
ans-=p;
}
return ans;
}
}Barrett;
