2015年蓝桥杯国赛C组机器人繁殖题解析：高精度整数代码实现与解题思路

一、题目解读

2015年蓝桥杯国赛C组“机器人繁殖”问题要求求解机器人按月繁殖的累计数量。题目设定初始机器人数量为a，每月新增b台，需计算n个月后总机器人数。由于繁殖数量可能呈指数级增长，普通整数类型无法存储结果，因此需采用高精度整数运算解决。

二、解题思路

核心在于自定义高精度整数类（BigInt），支持加法、减法及乘法操作。解题关键在于利用高精度加法模拟每月繁殖过程：每月总数为上月总数+新增数量，通过循环迭代计算n个月后的累计值。高精度处理避免了数据溢出，确保结果正确性。

三、解题步骤

初始化：读入初始数量a、新增量b及月份n，将a、b转换为高精度整数对象。
循环迭代：通过循环执行n次加法操作，每次将当前总数加上b，更新总数。
输出结果：将最终高精度整数转换为字符串输出，确保格式正确。

四、代码与注释

#include <iostream>
#include <string>
#include <vector>
using namespace std;

// 高精度整数类
class BigInt {
private:
    vector<int> digits;  // 存储数字各位（逆序）
    bool isNegative;     // 负数标记

public:
    BigInt() : isNegative(false) {}  // 默认构造函数
    BigInt(string s) {  // 字符串初始化
        if (s.empty()) return;
        isNegative = (s[0] == '-');  // 处理负号
        for (int i = s.size() - 1; i >= (isNegative? 1 : 0); --i) {
            digits.push_back(s[i] - '0');  // 逆序存储数字字符
        }
    }

    // 加法
    BigInt operator+(const BigInt& other) const {
        BigInt result;
        int carry = 0;  // 进位
        int maxLen = max(digits.size(), other.digits.size());

        for (int i = 0; i < maxLen || carry; ++i) {
            int sum = carry;
            if (i < digits.size()) sum += digits[i];
            if (i < other.digits.size()) sum += other.digits[i];
            result.digits.push_back(sum % 10);
            carry = sum / 10;
        }

        return result;
    }

    // 减法
    BigInt operator-(const BigInt& other) const {
        BigInt result;
        int borrow = 0;  // 借位

        for (int i = 0; i < digits.size(); ++i) {
            int diff = digits[i] - borrow;
            if (i < other.digits.size()) diff -= other.digits[i];
            if (diff < 0) {
                diff += 10;
                borrow = 1;
            } else {
                borrow = 0;
            }
            result.digits.push_back(diff);
        }

        // 去除前导零
        while (result.digits.size() > 1 && result.digits.back() == 0) {
            result.digits.pop_back();
        }

        return result;
    }

    // 乘法
    BigInt operator*(const BigInt& other) const {
        BigInt result;
        result.digits.resize(digits.size() + other.digits.size(), 0);

        for (int i = 0; i < digits.size(); ++i) {
            int carry = 0;
            for (int j = 0; j < other.digits.size() || carry; ++j) {
                long long product = result.digits[i + j] + 
                                   (long long)digits[i] * (j < other.digits.size() ? other.digits[j] : 0) + 
                                   carry;
                result.digits[i + j] = product % 10;
                carry = product / 10;
            }
        }

        // 去除前导零
        while (result.digits.size() > 1 && result.digits.back() == 0) {
            result.digits.pop_back();
        }

        return result;
    }

    // 除法
    BigInt operator/(const BigInt& other) const {
        BigInt quotient, remainder;

        for (int i = digits.size() - 1; i >= 0; --i) {
            remainder = remainder * BigInt("10") + BigInt(to_string(digits[i]));
            int count = 0;
            while (remainder >= other) {
                remainder = remainder - other;
                count++;
            }
            quotient.digits.insert(quotient.digits.begin(), count);
        }

        // 去除前导零
        while (quotient.digits.size() > 1 && quotient.digits.back() == 0) {
            quotient.digits.pop_back();
        }

        return quotient;
    }

    // 比较运算符
    bool operator>=(const BigInt& other) const {
        if (digits.size() != other.digits.size()) {
            return digits.size() > other.digits.size();
        }
        for (int i = digits.size() - 1; i >= 0; --i) {
            if (digits[i] != other.digits[i]) {
                return digits[i] > other.digits[i];
            }
        }
        return true;
    }

    // 输出
    friend ostream& operator<<(ostream& os, const BigInt& num) {
        for (int i = num.digits.size() - 1; i >= 0; --i) {
            os << num.digits[i];
        }
        return os;
    }
};

// 计算2的幂
BigInt powerOfTwo(int n) {
    BigInt result("1");
    for (int i = 0; i < n; ++i) {
        result = result * BigInt("2");
    }
    return result;
}

int main() {
    int n;
    string s_str;
    cin >> n >> s_str;
    BigInt s(s_str);

    // 计算分子部分: s + 2^(n+1) - n - 2
    BigInt two_pow_n1 = powerOfTwo(n + 1);
    BigInt numerator = s + two_pow_n1 - BigInt(to_string(n + 2));

    // 计算分母部分: 2^(n+1) - 1
    BigInt denominator = two_pow_n1 - BigInt("1");

    // 计算结果: x = numerator / denominator
    BigInt x = numerator / denominator;

    cout << x << endl;

    return 0;
}