关于算法竞赛中快速乘的一些优化

在一些算法竞赛题目中经常遇到一些需要取模的乘法运算，一般都是会爆 $C++$ 中 $long\\;long$ 范围的。

以下的计算均只考虑正整数的情况。

所以有人按着快速幂的思想提出了 $O(logW)$ （ $W$ 是乘数）的快速乘。

inline long long mmul ( long long a, long long b, const long long& Mod )  {
	long long rt ( 0 ) ;
	for ( ; b ; b >>= 1, ( a <<= 1 ) %= Mod )
		if ( b & 1 )  {
			( rt += a ) %= Mod ;
		}
	return rt ;
}

复杂度好高吖！！！

也有加以思考提出 $O(1)$ 的使用大范围的 $long\\;double$ 的快速乘的。

inline long long mmul ( long long a, long long b, const long long& Mod )  {
    a %= Mod, b %= Mod ;
    return ( a * b - ( long long ) ( ( ( long double ) a * b + 0.5 ) / Mod ) * Mod ) % Mod ;
}

对于模数大于 $\\sqrt{LLong\\_MAX}$ 的，它也会爆掉（计算 $a\\cdot b$ 爆掉）。

但是上面的方法都有时间复杂度过高或者是常数大的缺点。

为什么不使用小学知识的乘法分配律来优化呢？

我们可以考虑提出一个把大数拆成两个数之和的形式，使得可以在 $long\\;long$ 范围内计算。

我们要计算 $a \\cdot b\\;mod\\;p$

设 $b=lf+rg$

那么原式为

$a\\cdot(lf+rg)\\;mod\\;p=((a\\cdot lf)\\;mod\\;p+(a\\cdot rg)\\;mod\\;p)\\;mod\\;p$

我们把 $lf$ 钦定为 $b$ 的二进制前 $x$ 位， $rg$ 为 $b$ 的后 $(64-x)$ 位。

$x$ 根据实际情况来定吧，实在不行把 $a,b$ 都拆了，可以应对模数大于 $\\sqrt{LLong\\_MAX}$ 的情况。

参考代码：

inline long long mmul ( long long a, long long b, const long long& Mod )  {
	long long lf = a * ( b >> 25LL ) % Mod * ( 1LL << 25 ) % Mod ;
        long long rg = a * ( b & ( ( 1LL << 25 ) - 1 ) ) % Mod ;
	return ( lf + rg ) % Mod ;
}

我随机了 $1e7$ 组数据，数据范围均为 $1e10$ 以内（对于第二种方法可能小小有失公正）。

使用环境（机房电脑）为：

i5-4590 @3.30GHz
4GB 内存
Windows 7系统（这个机房没有Linux系统......）
G++ 4.9.2

编译命令：

-O2 -std=c++11 -Wl,--stack=80000000 -Wall -Wconversion -Wextra

这是生成数据的 $generator$ ：

# include <bits/stdc++.h>

long long r ( )  {
	return ( rand ( ) << 15LL | rand ( ) ) << 16LL | ( ( rand ( ) << 15LL | rand ( ) ) ) ;
}

int main ( )  {
	srand ( time ( 0 ) ) ;
	freopen ( "in.txt", "w", stdout ) ;
	int T = 10000000 ;
	const long long Mod = 10000000000LL ;

	while ( T -- )  {
		long long a = r ( ) % Mod, b = r ( ) % Mod ;
		if ( a < 0 )  a += Mod ;
		if ( b < 0 )  b += Mod ;
		assert ( a >= 0 && b >= 0 ) ;
		printf ( "%lld %lld\
", a, b ) ;
	}
	return 0 ;
}

这是测试用的 $cpp$ 文件：

# include <bits/stdc++.h>

inline long long mmul1 ( long long a, long long b, const long long& Mod )  {
	long long lf = a * ( b >> 25LL ) % Mod * ( 1LL << 25 ) % Mod ;
    long long rg = a * ( b & ( ( 1LL << 25 ) - 1 ) ) % Mod ;
	return ( lf + rg ) % Mod ;
}

inline long long mmul2 ( long long a, long long b, const long long& Mod )  {
	long long rt ( 0 ) ;
	for ( ; b ; b >>= 1LL, ( a <<= 1LL ) %= Mod )
		if ( b & 1 )  {
			( rt += a ) %= Mod ;
		}
	return rt ;
}

inline long long mmul3 ( long long a, long long b, const long long& Mod )  {
    a %= Mod, b %= Mod ;
    return ( a * b - ( long long ) ( ( ( long double ) a * b + 0.5 ) / Mod ) * Mod ) % Mod ;
}

int main ( )  {
	freopen ( "in.txt", "r", stdin ) ;
	freopen ( "result.txt", "w", stdout ) ;
	int t1 ( 0 ), t2 ( 0 ), t3 ( 0 ) ;
	long long a, b, ans1, ans2, ans3 ;
	# define MOD 1000000007LL
	while ( ~ scanf ( "%lld%lld", & a, & b ) )  {
		int start = clock ( ) ;
		ans1 = mmul1 ( a, b, MOD ) ;
		t1 += clock ( ) - start ;
		start = clock ( ) ;
		ans2 = mmul2 ( a, b, MOD ) ;
		t2 += clock ( ) - start ;
		start = clock ( ) ;
		ans3 = mmul3 ( a, b, MOD ) ;
		t3 += clock ( ) - start ;
	//	fprintf ( stderr, "%lld %lld %lld\
", ans1, ans2, ans3 ) ;
		assert ( ans1 == ans2 && ans2 == ans3 ) ;
	}
	# undef MOD
	puts ( "test result :" ) ;
	printf ( "mmult1 : %.3lfs\
", 1.0 * t1 / CLOCKS_PER_SEC ) ;
	printf ( "mmult2 : %.3lfs\
", 1.0 * t2 / CLOCKS_PER_SEC ) ;
	printf ( "mmult3 : %.3lfs\
", 1.0 * t3 / CLOCKS_PER_SEC ) ;
	return 0 ;
}