卡常卡绝望了，这玩意救了我一命……特地翻开 usaco 的这道题找到了这玩意，usaco 吼！

考虑一个多次询问 a/b 或者 a%b，其中 b 是固定的，但是在编译时未知（比如输入确定），如果编译时已知那么设成 const 编译器会自动优化掉，这时候使用该算法可能会负优化……

假定一个足够大的 \(c\)（具体要有多大后面分析），考察基于被预处理时计算的常数 \(base=\left\lfloor\dfrac cb\right\rfloor\) 的实数 \(B=\dfrac{base}c\)。设 \(\left\lfloor\dfrac cb\right\rfloor=\dfrac cb-r\)，显然 \(r\in[0,1)\)。那么 \(\dfrac{\left\lfloor\dfrac cb\right\rfloor}c=\dfrac{\dfrac cb-r}c=\dfrac 1b-\dfrac rc\)。\(r\) 本身就小于 \(1\)，再除以一个足够大，感性理解可以认为是足够小。于是这玩意的值就很接近 \(b\) 的倒数。

考虑做除法，将 \(a\) 乘上 \(b\) 的近似倒数得到 \(\left(\dfrac 1b-\dfrac rc\right)\!a=\dfrac ab-\dfrac{ar}c\)。此时 \(\left|\dfrac{ar}c\right|\) 显然小于 \(\left|\dfrac ac\right|\)（至于为啥绝对值，因为 \(a\) 可能为负）。由于 \(c\) 足够大，所以这玩意是在 \((-1,1)\) 之间的。反过来，要满足这个值在 \((-1,1)\) 之间，\(c\) 的「足够大」至少要取到所有询问中 \(a\) 的 max。于是 \(\left\lfloor Ba\right\rfloor\in\left[\left\lfloor\dfrac ab\right\rfloor-1,\left\lfloor\dfrac ab\right\rfloor+1\right]\)，只要算出 \(\lfloor Ba\rfloor\) 然后上下微调即可。模的话，利用 \(a\bmod b=a-b\!\left\lfloor\dfrac ab\right\rfloor\) 即可得到答案。

\(\lfloor Ba\rfloor=\left\lfloor\dfrac{base\cdot a}c\right\rfloor\)。那么这玩意怎么快速算呢，不也要做除法吗。但是我们可以设 \(c\) 为 \(2\) 的整次幂，这样就可以通过位移来实现。一般情况下，快除不怎么用，常用的是快模，并且模数是 1e9 级别的。对加法取模，这个二年级学生都会，直接微调即可。对乘法快模就需要用到这个算法了，乘出来 \(a\) 大概是 1e18 级别，所以 \(c\) 要是 1e18，\(base\) 便是 1e9。那么 \(\lfloor Ba\rfloor\) 的计算式里 \(base\cdot a\) 就是 1e27 级别，需要用到 i128（当然如果不给用 i128 就 GG 了）。一般设 \(c=2^{64}\)。

经过我一上午的倒腾，我发现不要每次都微调是很快的，到最后再微调输出。有的时候例如快速幂指数模 \(b-1\)，不能是负数，这时候在快速幂函数里微调一下也没关系，反正快速幂的常数也不在这上面……下面是快模的板子：

typedef long long ll;
typedef __int128_t i128;
i128 _base=1;
inline ll mol(ll x){return x-mod*(_base*x>>64);}

//in main
_base=(_base<<64)/mod;

经测试，不开 O2 快模速度是直接 % 的 2 倍，开 O2 是 3 倍，关键时刻还是能起死回生的。（当然前提是模数编译时未知，话说输入模数的题并不是很多？（逃））