模取幂.cpp

来自「数值计算的例子和参考书籍」· C++ 代码 · 共 23 行

typedef unsigned int UINT; 

UINT Binary[33];

UINT Calc(UINT a, UINT b, UINT m)
{
	UINT i, j, k;
	k = (UINT) log2(b) + 1;
	Binary[0] = a % m;
	for(i = 1; i <= k; i++)
	{
		Binary[i] = (Binary[i - 1] * Binary[i - 1]) % m;
	}
	j = 1, i = 0;
	while(b > 0)
	{
		if(b % 2 != 0) j = (j * Binary[i]) % m;
		b /= 2;
		i++;
	}
	return j;
}