O(1)快速乘
求两个数相乘并取模,但是乘积超过了long long怎么办呢?
一般都是快速幂的思想快速乘,时间复杂度为log(n)很快了,这里提供一个更快的O(1)算法
inline long long multi(long long x,long long y,long long mod)
{
long long tmp=(x*y-(long long)((long double)x/mod*y+1.0e-8)*mod);
return tmp<0 ? tmp+mod : tmp;
}