2019-01-11 1 分钟读完 (大约 212 个字)

64位模数乘法

当模数是一个64位的整数时，乘法取模过程中就会溢出。

此时有两种解决方法

一种是采取与快速幂类似的思想，时间复杂度位$O(lg)$

long long mul(long long x, long long y, long long M)
{
	y = (y % M + M) % M;
	long long ans = 0;
	long long tmp = x;
	while (y)
	{
		if (y & 1)
		{
			ans = (ans + tmp) % M;
		}
		tmp = (tmp + tmp) % M;
		y >>= 1;
	}
	return ans;
}

还有一种是利用long double来进行运算，有可能会计算错误，但时间复杂度是$O(1)$的

long long mul(long long x, long long y, long long M)
{
	return (x * y - (long long)((long double)x / M * y) * M + M) % M;
}

看起来很奇妙是不是？。。。玄学的一匹

摘自2009年国家集训队论文，骆可强：《论程序底层优化的一些方法与技巧》

# 黑科技

文章

分类

标签

关注我

64位模数乘法

目录

标签云

归档

Your browser is out-of-date!