O(1) 慢速乘

orginal: https://www.cnblogs.com/812-xiao-wen/p/10543023.html

inline ll ksc(ll x,ll y,ll p){
    ll z=(ld)x/p*y;
    ll res=(ull)x*y-(ull)z*p;
    return (res+p)%p;
}
// ll 表示 long long
// ld 表示 long double
// ull 表示 unsigned long long
// 一种自动溢出的数据类型（存满了就会自动变为0）

看到这份代码有没有感到十分奇怪？ 它中间是直接用了乘法操作的啊！这不直接爆掉了吗？

但是它就是可以算出正确答案来。因为它其实很巧妙的运用了自动溢出这个操作，我们的代码中的z就表示 ⌊x×y/p⌋ ，所以我们要求的就变成了 x×y−⌊x×y/p⌋×p ，虽然这两个部分都是会溢出的，但（unsigned）保证了它们溢出后的差值基本不变，所以即使它会溢出也不会影响最终结果的！

我们知道快速乘的原理其实就是乘法转加法（上面这种不算），但是这是可以根据题目性质灵活转变的，我们如何转成加法决定了我们的复杂度，就像如果模数并没有超过int范围很多，那我们适当的运用乘法分配律可以让复杂度非常接近 O(1) ：

inline ll ksc(ll x, ll y, ll P){
    ll L=x*(y>>25)%P*(1<<25)%P;
    ll R=x*(y&((1<<25)-1))%P;
    return (L+R)%P;
}

在保证运算不会爆long long的前提下，我们可以尽量优化其复杂度，就像上述代码在模数小于 10^12 的情况下完全变成了 O(1) 级别，在某些题目中会十分优秀！

光速幂

\sqrt {b} 预处理. 根号分治， O(1) 计算。