当模数 m 大于 232(甚至是 1018 级别)时,计算 a×bmodm 不能直接用 long long 计算,因为会爆。
一种解决方法是用加法模拟乘法,另外还可以强转 __int128,但都比较慢。
老师教过一种方法(LL 表示 long long):
LL mul(LL x, LL y, LL m)
{
LL res = x * y - (LL)((long double)x * y / m + 1e-8) * m;
return res < 0 ? res + m : res;
}
之前使用一直没有出问题。
但是昨天做一道需要用 Pollard-Rho 的题用这个方法做乘法,但 T 了,且原因在 Pollard-Rho 上面,然后把 long long 换成 __int128,long double 换成 __float128 就过了。
请问是这种方法有什么问题吗,有哪些地方需要改进的,以及是不是应该修改上面代码中 +1e-8。