luogu1226 取余运算||快速幂

题目大意：快速求$a^b\mod p$的值。

根据二进制，令$b=\sum t_k\cdot 2^k, t\in \{0,1\}$，那么$$a^b=a^{\sum t_k\cdot 2^k}\mod p=\prod a^{t_k \cdot 2^k}\mod p$$。$k$表示当前处理的$b$的二进制数的位数，$t_k$的取值取决于当前$b$的二进制位$k$上的值是$0$还是$1$。

同理，为了防止乘法越界，还要进行快速乘法。$$ab\mod p=\sum t_k\cdot a\cdot 2^k\mod p$$，各项解释与上相同。

#include <cstdio>

using namespace std;

#define LL long long

LL mul(LL a, LL b, LL p)

{

	LL ans = 0;

	while (b)

	{

		if (b & 1)

			ans = (ans + a) % p;

		a = (a + a) % p;

		b >>= 1;

	}

	return ans;

}

LL power(LL a, LL b, LL p)

{

	LL ans = 1;

	while (b)

	{

		if (b & 1)

			ans = mul(ans, a, p);//更新

		a = mul(a, a, p);//(a^2^k)^2=a^(2*2^k)=a^2^(k+1)

		b >>= 1;//b的二进制下一位

	}

	return ans;

}

int main()

{

	LL a, b, p;

	scanf("%lld%lld%lld", &a, &b, &p);

	printf("%lld^%lld mod %lld=%lld\n", a, b, p, power(a, b, p));

	return 0;

}

巴特西

luogu1226 取余运算||快速幂

最新文章

热门文章