2015年蓝桥杯国赛C组机器人繁殖（洛谷P8629）：高精度计算实战

21小时前比赛题解41

一、问题背景

题目模拟了机器人在n年后的繁殖情况，要求计算初始机器人数量x。每年每个机器人会繁殖出一个新机器人，同时所有机器人(包括新生)都会继续存活。这是一个典型的递推问题，由于数字可能非常大，需要使用高精度计算。

二、完整代码解析（含详细注释）

#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的n次幂
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;   // n年后的总数
    cin >> n >> s_str;
    BigInt s(s_str); // 转换为高精度数
    
    // 根据递推公式计算初始数量x
    BigInt two_pow_n1 = powerOfTwo(n + 1);
    BigInt numerator = s + two_pow_n1 - BigInt(to_string(n + 2));
    BigInt denominator = two_pow_n1 - BigInt("1");
    BigInt x = numerator / denominator;
    
    cout << x << endl;
    
    return 0;
}