取模运算相关的常数优化

首先，若模数 \(P=2^{32},2^{64}\)，直接利用 unsigned , unsigned long long 自然溢出即可，方便而且快。

若 \(P\) 是其它 2 的整数次幂，可以通过位运算优化取模：用 x&(P-1) 代替 x%P 。（这种情况好像基本没见过）

若 \(P\) 很小，例如 \(P=2022\) ，那么可以放心地用 int ，少量取模保证不溢出即可。

大部分情况下，\(P\) 是一个大质数（其实不是质数也没关系），而且常见模数中最大的是 \(10^9+7\) 。
这时一次乘法就会有爆 int 的风险，但一次加减法不会。
仍然可以全程用 int 。例如当 \(0\le x,y 时，
x=(x+y)%P; 可写成 (x+=y)>=P&&(x-=P);
x=(x-y+P)%P; 可写成 (x-=y)<0&&(x+=P);
避免了取模，也不会溢出
乘法可以写 x=1ll*x*y%P; ，但这个未必比直接开 long long 然后 (x*=y)%=P; 快
综合下来也不知道是 int 好还是 long long 好。（
个人偏好 int

如果优化加减法取模还不行的话，可以优化乘法取模

inline int mul(int x,int y,int P) { // x*y%P
    int t=1ll*x*y-(long long)(x*1./P*y+0.5)*P;
    return (t<0?t+P:t);
}

用了会快 虽然不知道为啥

还有一个比较少见的技巧：预处理单位分数，优化除法

比如我们写完一道题，简单估算一下发现做了几百万次除法 \(x/y\)
然后我们发现 \(2\le y\le N=10^5\)

考虑如下操作：

...
const double eps=1e-14; // 一个极小的常量
double inv[N+10];
inline int Div(int x,int y) { return x*inv[y]; }
    ...
    for (int i=2; i<=N; ++i) inv[i]=1./i+eps; // +eps 是为了防止精度损失
    ...

用 Div(x,y) 计算 x/y 。总体会快很多。
原理：浮点数乘法比整数除法快一点。
在特定场合下很有效。