政治文化研究网

小白快速了解快速幂法和逆元法及其用途

理论纵横 2021-10-25 06:59197网络整理政治文化研究网

小白快速了解快速幂法和逆元法及其用途

之前没学过快幂法和逆元法,写完这个问题才知道。新手抓紧时间!说说我的理解吧。

快速幂法:我们知道要找到a^b%N幂数列求和纵横理论,当b很大时需要大量的计算。快速的功率大大减少了计算时间。我们将 b 转换为 2 的多个幂。 首先,我们需要知道一个数模运算:

a*b%N=(a%N)*(b%N) (b+a)%N=b%N+a%N....... 除除法不能直接调制外,其他和普通的计算差不多

除法不能直接取模,需要逆元法!!!

例如: b=13: 13=1101(2), 所以 b=2^0+2^2+2^3;

原本需要计算13次,现在只需要计算3次即可计算出答案:以下是快速求幂的代码:

long long q_power(long long  a,long long b)//a^b 记得%N
{
	long long ans=1;
	while(b)
	{
		if(b&1)//b的二进制的最后一位是1
		    {
                ans=ans*a%N;
            }
		a=a*a%N;//依次求次方,但是不能超过模
		b>>=1;//把b的二进制的往前移动,去掉已经计算过的那位数
	}
	return ans;
}

记得每次都取模(取模要视情况而定,这个问题需要取)

PS:这个方法N表示要取模的数必须是素数!!!, 这是非常重要的。

下一步是逆元法。求解除法取模的情况,用逆元法将除法变为乘法:

首先,你需要知道费马小定理:

1. a和N的最大公约数是1幂数列求和纵横理论,gcd(a,N)=1;//N就是我们需要取模的数

2.a^(N-1)%N=1;//飞马小定理,自己百度,只知道怎么用。

3.简单变形:

a^(N-1)%N=1

a^(N-2)*a%N=1

a^(N-2)%n=1/a

所以我们可以把除法变成乘法:1/a = a^(N-2)%N

知道了这一点,我们就可以去AC了

#include
#define N 1000000007
/**
1.快速幂法 
2.逆元法》》把除数的模变成可以模的 
*/
long long q_power(long long  a,long long b)//a^b 记得%N
{
	long long ans=1;
	while(b)
	{
		if(b&1)//b的二进制的最后一位是1
		    {
                ans=ans*a%N;
            }
		a=a*a%N;//依次求次方,但是不能超过模
		b>>=1;//把b的二进制的往前移动,去掉已经计算过的那位数
	}
	return ans;
}
int main()
{
	long long m,n;
	scanf("%lld",&n);
//* a1*(q^(n+1)-1)/2  等比数列公式,然后把2进行逆元*/ 
	m=(q_power(3,n+1)-1);
	n=q_power(2,N-2);
	printf("%lld\n",(m*n)%N);
	return 0;
}

使用展开欧几里得的方法求逆元:展开欧几里得求逆元