时间复杂度为O(1)的两个数相乘结果超过long long取模的快速运算
ll multi(ll x,ll y){
ll ans = (x * y - (ll)((long double)x / mod * y + 1.0e-8) * mod);
return ans < 0 ? ans + mod : ans;
}
还有一种O(logn)的方法,这种方法虽然慢,但是精确,上面的方法在mod较大的情况下可能会失精
ll multi(ll a,ll b){
ll ans = 0;
while(b){
if(b & 1) ans = (ans + a) % mod;
a = (a << 1) % mod;
b >>= 1;
}
return ans;
}