快速乘
16年北京网络赛遇到了这个技巧...但是竟然忘记记了下来？
快速乘是为了解决 计算a_b % mod 时a_b溢出LL 的问题
比如a=1E16,b=1E16,mod=1E18，虽然最后的结果没有溢出，但是中间溢出了。
原理和快速幂很类似，具体可以参考 晴川大爷的专栏
1ll fastMultiplication(ll a,ll b,ll mod){
2 ll ans = 0;
3 while(b){
4 if(b%2==1){
5 b--;
6 ans = ans + a;
7 ans %= mod;
8 }else{
9 b /= 2;
10 a = a + a;
11 a %= mod;
12 }
13 }
14 return ans;
15}
完全就是把快速幂中的乘法变成加法了嘛（从记忆角度考虑orz
1inline long long multi(long long x,long long y,long long mod)
2{
3long long tmp=(x*y-(long long)((long double)x/mod*y+1.0e-8)*mod);
4return tmp<0 ? tmp+mod : tmp;
5}