萌新求助,关于大数乘法取模
  • 板块学术版
  • 楼主teylnol_evteyl
  • 当前回复6
  • 已保存回复7
  • 发布时间2023/12/13 15:06
  • 上次更新2023/12/13 17:58:14
查看原帖
萌新求助,关于大数乘法取模
636142
teylnol_evteyl楼主2023/12/13 15:06

当模数 mm 大于 2322^{32}(甚至是 101810^{18} 级别)时,计算 a×b mod ma\times b\bmod m 不能直接用 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。

2023/12/13 15:06
加载中...