B3739 题解

残阳如血 · 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;
}