神奇的操作--O(1)快速乘

时间:2021-01-22 12:26:16

从同机房大佬那里听来的...

用O(1)时间求出两个相乘超过long long的数的取摸的结果

神奇的操作...

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;
}

 据说如果模数过大可能导致精度误差..反正我是没遇到过....