LuoguB2075 幂的末尾题解

Content

求 \(a^b\) 的末三位。

数据范围：\(1\leqslant a\leqslant 100\)，\(1\leqslant b\leqslant 10^4\)。

Solution

先讲一个性质：\(a^b\bmod1000\) 再补下前导 \(0\) 得出来的就是 \(a^b\) 的末三位。

所以说直接暴力算出来？确实也可行，直接循环，一边循环一边模，最后补齐了 \(0\) 输出即可。

那么想到幂的模还可以想到什么？没错！快速幂可以解决这个问题。如果没学过快速幂的可以前往P1226快速幂模板题的题解中更好地理解快速幂。这里主要放上来的是快速幂的代码。

Code

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <iostream>

using namespace std;

long long n, p;

long long quickPow(long long a, long long b, long long k) {

	if(k == 1)	return 0;

	long long ans = 1;

	while(b) {

		if(b & 1)	ans = ans * a % k;

		a = a * a % k;

		b >>= 1;

	}

	return ans;

}

int main() {

	scanf("%lld%lld", &n, &p);

	return printf("%03lld", quickPow(n, p, 1000)), 0; //还记得 "%03lld" 是什么意思吗？不知道的可以前往我的 B2001 的题解查看。

}

巴特西

LuoguB2075 幂的末尾题解

Content

Solution

Code

最新文章

热门文章

巴特西

LuoguB2075 幂的末尾 题解

Content

Solution

Code

最新文章

热门文章

LuoguB2075 幂的末尾题解