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

胡志明t

一、题目解读

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

二、解题思路

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

三、解题步骤

1. 初始化：读入初始数量a、新增量b及月份n，将a、b转换为高精度整数对象。

2. 循环迭代：通过循环执行n次加法操作，每次将当前总数加上b，更新总数。

3. 输出结果：将最终高精度整数转换为字符串输出，确保格式正确。

四、代码与注释

1. #include <iostream>
   
2. #include <string>
   
3. #include <vector>
   
4. using namespace std;
   
5. 
   
6. // 高精度整数类
   
7. class BigInt {
   
8. private:
   
9.     vector<int> digits;  // 存储数字各位（逆序）
   
10.     bool isNegative;     // 负数标记
    
11. 
    
12. public:
    
13.     BigInt() : isNegative(false) {}  // 默认构造函数
    
14.     BigInt(string s) {  // 字符串初始化
    
15.         if (s.empty()) return;
    
16.         isNegative = (s[0] == '-');  // 处理负号
    
17.         for (int i = s.size() - 1; i >= (isNegative? 1 : 0); --i) {
    
18.             digits.push_back(s[i] - '0');  // 逆序存储数字字符
    
19.         }
    
20.     }
    
21. 
    
22.     // 加法
    
23.     BigInt operator+(const BigInt& other) const {
    
24.         BigInt result;
    
25.         int carry = 0;  // 进位
    
26.         int maxLen = max(digits.size(), other.digits.size());
    
27. 
    
28.         for (int i = 0; i < maxLen || carry; ++i) {
    
29.             int sum = carry;
    
30.             if (i < digits.size()) sum += digits[i];
    
31.             if (i < other.digits.size()) sum += other.digits[i];
    
32.             result.digits.push_back(sum % 10);
    
33.             carry = sum / 10;
    
34.         }
    
35. 
    
36.         return result;
    
37.     }
    
38. 
    
39.     // 减法
    
40.     BigInt operator-(const BigInt& other) const {
    
41.         BigInt result;
    
42.         int borrow = 0;  // 借位
    
43. 
    
44.         for (int i = 0; i < digits.size(); ++i) {
    
45.             int diff = digits[i] - borrow;
    
46.             if (i < other.digits.size()) diff -= other.digits[i];
    
47.             if (diff < 0) {
    
48.                 diff += 10;
    
49.                 borrow = 1;
    
50.             } else {
    
51.                 borrow = 0;
    
52.             }
    
53.             result.digits.push_back(diff);
    
54.         }
    
55. 
    
56.         // 去除前导零
    
57.         while (result.digits.size() > 1 && result.digits.back() == 0) {
    
58.             result.digits.pop_back();
    
59.         }
    
60. 
    
61.         return result;
    
62.     }
    
63. 
    
64.     // 乘法
    
65.     BigInt operator*(const BigInt& other) const {
    
66.         BigInt result;
    
67.         result.digits.resize(digits.size() + other.digits.size(), 0);
    
68.         
    
69.         for (int i = 0; i < digits.size(); ++i) {
    
70.             int carry = 0;
    
71.             for (int j = 0; j < other.digits.size() || carry; ++j) {
    
72.                 long long product = result.digits[i + j] +
    
73.                                    (long long)digits[i] * (j < other.digits.size() ? other.digits[j] : 0) +
    
74.                                    carry;
    
75.                 result.digits[i + j] = product % 10;
    
76.                 carry = product / 10;
    
77.             }
    
78.         }
    
79.         
    
80.         // 去除前导零
    
81.         while (result.digits.size() > 1 && result.digits.back() == 0) {
    
82.             result.digits.pop_back();
    
83.         }
    
84.         
    
85.         return result;
    
86.     }
    
87.    
    
88.     // 除法
    
89.     BigInt operator/(const BigInt& other) const {
    
90.         BigInt quotient, remainder;
    
91.         
    
92.         for (int i = digits.size() - 1; i >= 0; --i) {
    
93.             remainder = remainder * BigInt("10") + BigInt(to_string(digits[i]));
    
94.             int count = 0;
    
95.             while (remainder >= other) {
    
96.                 remainder = remainder - other;
    
97.                 count++;
    
98.             }
    
99.             quotient.digits.insert(quotient.digits.begin(), count);
    
100.         }
     
101.         
     
102.         // 去除前导零
     
103.         while (quotient.digits.size() > 1 && quotient.digits.back() == 0) {
     
104.             quotient.digits.pop_back();
     
105.         }
     
106.         
     
107.         return quotient;
     
108.     }
     
109.    
     
110.     // 比较运算符
     
111.     bool operator>=(const BigInt& other) const {
     
112.         if (digits.size() != other.digits.size()) {
     
113.             return digits.size() > other.digits.size();
     
114.         }
     
115.         for (int i = digits.size() - 1; i >= 0; --i) {
     
116.             if (digits[i] != other.digits[i]) {
     
117.                 return digits[i] > other.digits[i];
     
118.             }
     
119.         }
     
120.         return true;
     
121.     }
     
122.    
     
123.     // 输出
     
124.     friend ostream& operator<<(ostream& os, const BigInt& num) {
     
125.         for (int i = num.digits.size() - 1; i >= 0; --i) {
     
126.             os << num.digits[i];
     
127.         }
     
128.         return os;
     
129.     }
     
130. };
     
131. 
     
132. // 计算2的幂
     
133. BigInt powerOfTwo(int n) {
     
134.     BigInt result("1");
     
135.     for (int i = 0; i < n; ++i) {
     
136.         result = result * BigInt("2");
     
137.     }
     
138.     return result;
     
139. }
     
140. 
     
141. int main() {
     
142.     int n;
     
143.     string s_str;
     
144.     cin >> n >> s_str;
     
145.     BigInt s(s_str);
     
146.    
     
147.     // 计算分子部分: s + 2^(n+1) - n - 2
     
148.     BigInt two_pow_n1 = powerOfTwo(n + 1);
     
149.     BigInt numerator = s + two_pow_n1 - BigInt(to_string(n + 2));
     
150.    
     
151.     // 计算分母部分: 2^(n+1) - 1
     
152.     BigInt denominator = two_pow_n1 - BigInt("1");
     
153.    
     
154.     // 计算结果: x = numerator / denominator
     
155.     BigInt x = numerator / denominator;
     
156.    
     
157.     cout << x << endl;
     
158.    
     
159.     return 0;
     
160. }

复制代码

五、总结

本解法通过高精度整数类高效处理大数运算，核心在于加法操作的迭代应用。代码设计简洁，通过vector存储数字各位，支持动态扩展，适用于类似需要大数计算的竞赛题目。同时，减法与乘**能的实现为扩展其他复杂运算提供了基础。

来源：蓝桥杯题解