快速乘与快速幂

Tang7O

ACM算法

发布于：2020年4月9日

次浏览

字数统计: 205字   |   阅读时长: 1分

快速乘：(a*b)%c

原理：将b转化为二进制的形式 用b每一位的权重乘a再相加
举个例子：$20 10=20(1010)_2=(202^31) + (202^20) + (202^11) + (202^00)=160+40=200$
代码如下：

1
2
3
4
5
6
7
8
9
10
11
12

int fast_mul(int a,int b,int c)
{
	int ans=0;
	while(b)
	{
		if(b%2)
			ans=ans%c+a%c;
		a=(a%c+a%c)%c;
		b/=2;
	}
	return ans;
}

快速幂：(a^b)%c

原理：将b转化为二进制的形式 用a^(b每一位的权重的和)
举个例子： 11的二进制是1011, 11 = 2³×1 + 2²×0 + 2¹×1 + 2º×1，我们将a¹¹转化为算 $a^ {11}=a^ {(2^ 0+2^ 1+2^ 3)}=a^ {2^ 0}a^ {2^ 1}a^ {2^3}$
代码如下：

1
2
3
4
5
6
7
8
9
10
11
12

int fast_pow(int a,int b,int c)
{
	int ans=1;
	while(b)
	{
		if(b%2)
			ans=(ans%c*a%c)%c;
		a=(a%c*a%c)%c;
		b/=2;
	}
	return ans;
}

更新于：2022年4月13日

算法