【快速幂取模】fzu 1752 A^B mod C_C/C++_编程开发_程序员俱乐部

参考《算法艺术与信息学竞赛》：


题目：http://acm.fzu.edu.cn/problem.php?pid=1752
由于(1<=A,B,C<2^63)，所以要用到mul_mod二分求a*a，不然会溢出

原来的快速幂取模简单模板：

//求(a^b)%c
int qmod (int a, int b, int c)
{
	int res = 1;
	for ( ; b; b >>= 1)
	{
		if (b & 1)
			res = (LL)res * a % c; 
		a = (LL)a * a % c;
	}
	return res;
}

对于fzu 1752这题：
速度就这鬼样：

#include <iostream>
using namespace std;
#define ULL unsigned __int64

ULL mul_mod (ULL a, ULL b, ULL c) //利用快速取幂模的思想求a*a%c和res*a%c，为了防止溢出
{
	ULL res = 0;
	for ( ; b; b >>= 1)
	{
		if (b & 1)
		{
			res += a;    //这两句换成 res = (res + a) % c 会很慢
			if (res >= c) res -= c;
		}
		a <<= 1;    //这两句换成 a = (a + a) % c 也很慢
		if (a >= c) a -= c;
	}
	return res;
}

ULL qmod (ULL a, ULL b, ULL c)
{
	ULL res = 1;
	for ( ; b; b >>= 1)
	{
		if (b & 1)
			res = mul_mod (a, res, c);
		a = mul_mod (a, a, c);
	}
	return res;
}

int main()
{
	ULL a, b, c;
	while (~scanf ("%I64u%I64u%I64u", &a, &b, &c))
		printf ("%I64u\n", qmod (a%c, b, c));
    return 0;
}

• 
• 大小: 104.9 KB

• 
• 大小: 8.2 KB

• 查看图片附件