自动搬运

查看原文

来自洛谷，原作者为

	残阳如血 人事已尽，天命难违

搬运于2025-08-24 21:14:44，当前版本为作者最后更新于2023-09-30 14:22:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路分析

部分分

可以发现，$a^n<2^{32}$，所以可以用 unsigned long long 存下。

然后由于 $n\le100$，所以我们无需使用快速幂，直接求积即可。但我就是要写快速幂（

正解

高精度乘法的板子题。如果不会的可以去看 P1303，里面的题解有着比较详细的解释。这里不再赘述。代码有着比较详细的注释，可供读者理解。

代码演示

部分分

#include <iostream>
#include <algorithm>
typedef unsigned long long lint;

lint qpow(lint a, int b) { // 快速幂模板
	lint ans = 1;
	while (b) {
		if (b & 1) ans *= a;
		a *= a, b /= 2;
	}
	return ans;
}

int main() {
	lint a; int b;
	std::cin >> a >> b;
	std::string s = std::to_string(qpow(a, b)); // 将结果变为字符串方便统计
	int cnt1 = 0, cnt2 = 0;
	for (auto ch : s) { // 遍历每一个字符
		if ((ch - '0') & 1) cnt1++; // 如果是奇数字符
		else cnt2++;
	}
	std::cout << cnt1 - cnt2;
	return 0;
}

正解

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

std::string prod(std::string sa, std::string sb) {
	size_t la = sa.size(), lb = sb.size(); // 获得长度
	size_t lm = la + lb + 1;
	// 需要注意的是，乘法的最终结果长度可能为两个字符串长度之和
	std::vector<int> a(la), b(lb), c(lm); // std::vector 好操作
	for (size_t i = 0; i < la; ++i) a[i] = sa[la - i - 1] - '0';
	for (size_t i = 0; i < lb; ++i) b[i] = sb[lb - i - 1] - '0';
	for (size_t i = 0; i < la; ++i)
		for (size_t j = 0; j < lb; ++j)
			c[i + j] += a[i] * b[j]; // 一直往结果数组中存储
	for (size_t i = 0; i < lm - 1; ++i)
		c[i + 1] += c[i] / 10, c[i] %= 10; // 遍历一遍使其正常
	while (c.size() > 1 && c.back() == 0) c.pop_back(); // 去掉前导零
	std::string ans; // 结果字符串
	for (int i = c.size() - 1; i >= 0; --i) ans += c[i] + '0';
	return ans;
}

std::string pow(int a, int n) { // 求幂
	std::string ans = "1";
	std::string a1 = std::to_string(a);
	while (n--)
		ans = prod(ans, a1);
	return ans;
}

int main() {
	int a, n, cnt1 = 0, cnt2 = 0;
	std::cin >> a >> n;
	auto s = pow(a, n);
	for (auto ch : s) {
		if ((ch - '0') & 1) ++cnt1;
		else ++cnt2;
	}
	std::cout << cnt1 - cnt2;
	return 0;
}