#创作计划##创入计划#【普及组算法1】
2025-08-01 12:10:53
发布于：浙江
10阅读
0回复
0点赞
突发奇想，想出一个题单题解系列，今天是第一期《请输入文本》。高精度计算
先，放出高精度模板：
加法：
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
string addBigNumbers(string num1, string num2) {
if (num1.length() < num2.length()) {
swap(num1, num2);
}
string result;
int carry = 0;
int len1 = num1.length();
int len2 = num2.length();
for (int i = 0; i < len1; ++i) {
int digit1 = num1[len1 - 1 - i] - '0';
int digit2 = i < len2 ? num2[len2 - 1 - i] - '0' : 0;
int sum = digit1 + digit2 + carry;
carry = sum / 10;
result.push_back(sum % 10 + '0');
}
if (carry > 0) {
result.push_back(carry + '0');
}
reverse(result.begin(), result.end());
return result;
}
int main() {
string a, b;
cin >> a >> b;
string sum = addBigNumbers(a, b);
cout << sum << endl;
return 0;
}
减法
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
bool isLessThan(const string& num1, const string& num2) {
if (num1.length() != num2.length()) {
return num1.length() < num2.length();
}
for (int i = 0; i < num1.length(); ++i) {
if (num1[i] != num2[i]) {
return num1[i] < num2[i];
}
}
return false;
}
string subtractBigNumbers(string num1, string num2) {
bool isNegative = false;
if (isLessThan(num1, num2)) {
swap(num1, num2);
isNegative = true;
}
string result;
int borrow = 0;
int len1 = num1.length();
int len2 = num2.length();
for (int i = 0; i < len1; ++i) {
int digit1 = num1[len1 - 1 - i] - '0';
int digit2 = i < len2 ? num2[len2 - 1 - i] - '0' : 0;
int diff = digit1 - digit2 - borrow;
if (diff < 0) {
diff += 10;
borrow = 1;
} else {
borrow = 0;
}
result.push_back(diff + '0');
}
while (result.size() > 1 && result.back() == '0') {
result.pop_back();
}
if (isNegative) {
result.push_back('-');
}
reverse(result.begin(), result.end());
return result;
}
int main() {
string a, b;
cin >> a >> b;
string difference = subtractBigNumbers(a, b);
cout << difference << endl;
return 0;
}
乘法
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
string multiplyStrings(string num1, string num2) {
if (num1 == "0" || num2 == "0") return "0";
int len1 = num1.size();
int len2 = num2.size();
vector<int> result(len1 + len2, 0);
for (int i = len1 - 1; i >= 0; i--) {
for (int j = len2 - 1; j >= 0; j--) {
int product = (num1[i] - '0') * (num2[j] - '0');
int sum = product + result[i + j + 1];
result[i + j + 1] = sum % 10;
result[i + j] += sum / 10;
}
}
string res;
for (int num : result) {
if (!(res.empty() && num == 0)) {
res.push_back(num + '0');
}
}
return res.empty() ? "0" : res;
}
int main() {
string a, b;
cin >> a >> b;
cout << multiplyStrings(a, b) << endl;
return 0;
}
除法
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
pair<string, long long> divideStrings(string dividend, long long divisor) {
if (divisor == 0) {
return {"", 0};
}
string quotient;
long long remainder = 0;
for (char digit : dividend) {
remainder = remainder * 10 + (digit - '0');
quotient.push_back((remainder / divisor) + '0');
remainder %= divisor;
}
quotient.erase(0, quotient.find_first_not_of('0'));
if (quotient.empty()) quotient = "0";
return {quotient, remainder};
}
int main() {
string a;
long long b;
cin >> a >> b;
auto result = divideStrings(a, b);
cout << result.first << "\n" << result.second << endl;
return 0;
}
T1 A7870.高精度加法
无需多言，直接套公式。
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
string addBigNumbers(string num1, string num2) {
if (num1.length() < num2.length()) {
swap(num1, num2);
}
string result;
int carry = 0;
int len1 = num1.length();
int len2 = num2.length();
for (int i = 0; i < len1; ++i) {
int digit1 = num1[len1 - 1 - i] - '0';
int digit2 = i < len2 ? num2[len2 - 1 - i] - '0' : 0;
int sum = digit1 + digit2 + carry;
carry = sum / 10;
result.push_back(sum % 10 + '0');
}
if (carry > 0) {
result.push_back(carry + '0');
}
reverse(result.begin(), result.end());
return result;
}
int main() {
string a, b;
cin >> a >> b;
string sum = addBigNumbers(a, b);
cout << sum << endl;
return 0;
}
T2 A7871.高精度减法
依旧套公式：
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
bool isLessThan(const string& num1, const string& num2) {
if (num1.length() != num2.length()) {
return num1.length() < num2.length();
}
for (int i = 0; i < num1.length(); ++i) {
if (num1[i] != num2[i]) {
return num1[i] < num2[i];
}
}
return false;
}
string subtractBigNumbers(string num1, string num2) {
bool isNegative = false;
if (isLessThan(num1, num2)) {
swap(num1, num2);
isNegative = true;
}
string result;
int borrow = 0;
int len1 = num1.length();
int len2 = num2.length();
for (int i = 0; i < len1; ++i) {
int digit1 = num1[len1 - 1 - i] - '0';
int digit2 = i < len2 ? num2[len2 - 1 - i] - '0' : 0;
int diff = digit1 - digit2 - borrow;
if (diff < 0) {
diff += 10;
borrow = 1;
} else {
borrow = 0;
}
result.push_back(diff + '0');
}
while (result.size() > 1 && result.back() == '0') {
result.pop_back();
}
if (isNegative) {
result.push_back('-');
}
reverse(result.begin(), result.end());
return result;
}
int main() {
string a, b;
cin >> a >> b;
string difference = subtractBigNumbers(a, b);
cout << difference << endl;
return 0;
}
T3 A7872.数楼梯
这是一个斐波那契数列问题，但由于 可以达到 ，普通的整数类型会溢出，需要使用高精度计算。
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
class BigInteger {
private:
vector<int> digits;
void trim() {
while (digits.size() > 1 && digits.back() == 0) {
digits.pop_back();
}
}
public:
BigInteger() { digits.push_back(0); }
BigInteger(int num) {
if (num == 0) {
digits.push_back(0);
}
while (num > 0) {
digits.push_back(num % 10);
num /= 10;
}
}
BigInteger operator+(const BigInteger& other) const {
BigInteger result;
result.digits.clear();
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];
carry = sum / 10;
result.digits.push_back(sum % 10);
}
return result;
}
friend ostream& operator<<(ostream& os, const BigInteger& num) {
for (int i = num.digits.size() - 1; i >= 0; --i) {
os << num.digits[i];
}
return os;
}
};
int main() {
int N;
cin >> N;
if (N <= 2) {
cout << N << endl;
return 0;
}
BigInteger a(1), b(2), c;
for (int i = 3; i <= N; ++i) {
c = a + b;
a = b;
b = c;
}
cout << b << endl;
return 0;
}
解题思路
-
问题分析：一个典型的斐波那契数列问题，
-
高精度需求：当 时，结果会非常大，远超普通数据类型的表示范围,所以“请输入文本”（开玩笑
-
实现方法：
- 自定义BigInteger类处理大整数
- 实现加法运算
- 迭代计算斐波那契数列
T4 A7873.回文数
需要在给定的 进制下判断一个数是否为回文数，如果不是则进行反转相加操作，直到得到回文数或超过30步。
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
// 判断是否为回文数
bool isPalindrome(const string& s) {
for (int i = 0; i < s.size() / 2; i++) {
if (s[i] != s[s.size() - 1 - i]) {
return false;
}
}
return true;
}
// 将字符转换为对应的数值
int charToValue(char c) {
if (c >= '0' && c <= '9') return c - '0';
if (c >= 'A' && c <= 'F') return c - 'A' + 10;
return 0;
}
// 将数值转换为对应的字符
char valueToChar(int v) {
if (v < 10) return '0' + v;
return 'A' + v - 10;
}
// N进制高精度加法
string addInBase(const string& a, const string& b, int base) {
string result;
int carry = 0;
int len = max(a.size(), b.size());
for (int i = 0; i < len || carry; i++) {
int digitA = i < a.size() ? charToValue(a[a.size() - 1 - i]) : 0;
int digitB = i < b.size() ? charToValue(b[b.size() - 1 - i]) : 0;
int sum = digitA + digitB + carry;
carry = sum / base;
result.push_back(valueToChar(sum % base));
}
reverse(result.begin(), result.end());
return result;
}
// 处理回文数问题
void solvePalindrome(int N, string M) {
int steps = 0;
while (steps <= 30) {
if (isPalindrome(M)) {
cout << "STEP=" << steps << endl;
return;
}
string reversedM = M;
reverse(reversedM.begin(), reversedM.end());
M = addInBase(M, reversedM, N);
steps++;
}
cout << "Impossible!" << endl;
}
int main() {
int N;
string M;
cin >> N >> M;
// 去除前导零
while (M.size() > 1 && M[0] == '0') {
M.erase(0, 1);
}
solvePalindrome(N, M);
return 0;
}
代码解析
-
回文判断：
isPalindrome函数检查字符串是否为回文 -
进制转换：
charToValue将字符转换为对应进制的数值valueToChar将数值转换为对应字符
-
高精度加法：
addInBase实现 进制的高精度加法 -
主逻辑：
- 最多进行30步操作
- 每步检查是否为回文数
- 不是则反转相加
- 超过30步输出"Impossible!"
关键点
-
进制处理：支持2-10进制和16进制
-
大数处理：使用字符串进行高精度运算
-
效率优化：直接操作字符串，避免不必要的转换
-
边界条件：处理前导零和即时回文数情况
T5 B进制星球
代码：
#include <iostream>
#include <string>
#include <algorithm>
#include <cctype>
using namespace std;
// 将字符转换为对应的数值
int charToValue(char c) {
if (isdigit(c)) return c - '0';
if (isalpha(c)) return toupper(c) - 'A' + 10;
return 0;
}
// 将数值转换为对应的字符
char valueToChar(int v) {
if (v < 10) return '0' + v;
return 'A' + v - 10;
}
// B进制高精度加法
string addInBase(const string& num1, const string& num2, int B) {
string result;
int carry = 0;
int len1 = num1.length();
int len2 = num2.length();
int maxLen = max(len1, len2);
for (int i = 0; i < maxLen || carry; ++i) {
int digit1 = i < len1 ? charToValue(num1[len1 - 1 - i]) : 0;
int digit2 = i < len2 ? charToValue(num2[len2 - 1 - i]) : 0;
int sum = digit1 + digit2 + carry;
carry = sum / B;
result.push_back(valueToChar(sum % B));
}
// 反转结果字符串
reverse(result.begin(), result.end());
// 去除前导零
size_t nonZero = result.find_first_not_of('0');
if (nonZero != string::npos) {
result = result.substr(nonZero);
} else {
result = "0"; // 全零的情况
}
return result;
}
int main() {
int B;
string num1, num2;
cin >> B;
cin >> num1 >> num2;
string sum = addInBase(num1, num2, B);
cout << sum << endl;
return 0;
}
代码解析：
-
字符转换函数：
charToValue：将字符转换为对应的数值（支持0-9和A-Z）valueToChar：将数值转换为对应的字符
-
高精度加法：
-
从最低位开始逐位相加
-
处理不同长度的数字
-
正确处理进位（基于给定的进制B）
-
反转结果字符串（因为是从低位开始计算的）
- 前导零处理：
-
去除结果中的前导零
-
处理全零的特殊情况
- 输入输出：
-
读取进制B和两个B进制数
-
输出相加后的结果
关键点
-
进制支持：完整支持2-36进制的运算
-
大数处理：可以处理长达2000位的数字
-
字符转换：正确处理数字和字母的转换
-
前导零处理：确保输出结果规范
-
效率优化：时间复杂度为O(n)，适合大数运算
T6 A7875.A*B Problem
套公式（×3）
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
string multiplyStrings(string num1, string num2) {
if (num1 == "0" || num2 == "0") return "0";
int len1 = num1.size();
int len2 = num2.size();
vector<int> result(len1 + len2, 0);
for (int i = len1 - 1; i >= 0; i--) {
for (int j = len2 - 1; j >= 0; j--) {
int product = (num1[i] - '0') * (num2[j] - '0');
int sum = product + result[i + j + 1];
result[i + j + 1] = sum % 10;
result[i + j] += sum / 10;
}
}
string res;
for (int num : result) {
if (!(res.empty() && num == 0)) {
res.push_back(num + '0');
}
}
return res.empty() ? "0" : res;
}
int main() {
string a, b;
cin >> a >> b;
cout << multiplyStrings(a, b) << endl;
return 0;
}
T7 A7876.A/B Problem
套公式（×4）
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
string multiplyStrings(string num1, string num2) {
if (num1 == "0" || num2 == "0") return "0";
int len1 = num1.size();
int len2 = num2.size();
vector<int> result(len1 + len2, 0);
for (int i = len1 - 1; i >= 0; i--) {
for (int j = len2 - 1; j >= 0; j--) {
int product = (num1[i] - '0') * (num2[j] - '0');
int sum = product + result[i + j + 1];
result[i + j + 1] = sum % 10;
result[i + j] += sum / 10;
}
}
string res;
for (int num : result) {
if (!(res.empty() && num == 0)) {
res.push_back(num + '0');
}
}
return res.empty() ? "0" : res;
}
int main() {
string a, b;
cin >> a >> b;
cout << multiplyStrings(a, b) << endl;
return 0;
}
T8 A7877.阶乘之和
代码：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class BigInteger {
private:
vector<int> digits; // 低位在前存储
public:
BigInteger() { digits.push_back(0); }
BigInteger(int num) {
if (num == 0) {
digits.push_back(0);
}
while (num > 0) {
digits.push_back(num % 10);
num /= 10;
}
}
// 高精度加法
BigInteger operator+(const BigInteger& other) const {
BigInteger result;
result.digits.clear();
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];
carry = sum / 10;
result.digits.push_back(sum % 10);
}
return result;
}
// 高精度乘法
BigInteger operator*(const BigInteger& other) const {
BigInteger 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) {
int product = result.digits[i + j] + digits[i] *
(j < other.digits.size() ? other.digits[j] : 0) + carry;
carry = product / 10;
result.digits[i + j] = product % 10;
}
}
// 去除前导零
while (result.digits.size() > 1 && result.digits.back() == 0) {
result.digits.pop_back();
}
return result;
}
friend ostream& operator<<(ostream& os, const BigInteger& num) {
for (int i = num.digits.size() - 1; i >= 0; --i) {
os << num.digits[i];
}
return os;
}
};
int main() {
int n;
cin >> n;
BigInteger sum(0);
BigInteger factorial(1);
for (int i = 1; i <= n; ++i) {
// 计算i! = (i-1)! * i
factorial = factorial * BigInteger(i);
sum = sum + factorial;
}
cout << sum << endl;
return 0;
}
代码解析
- BigInteger类：
-
使用
vector<int>存储大数，低位在前 -
实现了高精度加法和乘法运算
-
支持从整数构造
- 阶乘计算：
-
利用递推关系：
-
每次迭代更新当前阶乘值
- 求和过程：
-
初始化sum为0
-
依次计算1!到n!并累加到sum中
- 输出结果：
- 从高位到低位输出最终的和
关键点
-
高精度实现：自定义BigInteger类处理大数运算
-
效率优化：递推计算阶乘，避免重复计算
-
内存管理：动态调整数字位数，去除前导零
-
边界处理：正确处理n=1的特殊情况
T9 A7878.阶乘数码（请输入文本（A7878
代码：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class BigInteger {
private:
vector<int> digits; // 低位在前存储
public:
BigInteger() { digits.push_back(0); }
BigInteger(int num) {
if (num == 0) {
digits.push_back(0);
}
while (num > 0) {
digits.push_back(num % 10);
num /= 10;
}
}
// 高精度乘法
BigInteger operator*(const BigInteger& other) const {
BigInteger 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) {
int product = result.digits[i + j] + digits[i] *
(j < other.digits.size() ? other.digits[j] : 0) + carry;
carry = product / 10;
result.digits[i + j] = product % 10;
}
}
// 去除前导零
while (result.digits.size() > 1 && result.digits.back() == 0) {
result.digits.pop_back();
}
return result;
}
// 统计数字a出现的次数
int countDigit(int a) const {
int count = 0;
for (int digit : digits) {
if (digit == a) {
count++;
}
}
return count;
}
};
int main() {
int t;
cin >> t;
while (t--) {
int n, a;
cin >> n >> a;
BigInteger factorial(1);
for (int i = 2; i <= n; ++i) {
factorial = factorial * BigInteger(i);
}
cout << factorial.countDigit(a) << endl;
}
return 0;
}
代码解析
- BigInteger类：
-
使用
vector<int>存储大数，低位在前 -
实现高精度乘法运算
-
添加
countDigit方法统计特定数字出现次数
- 阶乘计算：
-
初始化factorial为1
-
通过循环计算
- 数字统计：
-
遍历阶乘结果的每一位数字
-
统计目标数字a的出现次数
关键点
-
高精度计算：正确处理n≤1000时的超大阶乘
-
数字统计：直接遍历存储的数字进行统计
-
效率优化：递推计算阶乘，避免重复计算
-
内存管理：动态调整数字位数，去除前导零
T10 A7879.最大乘积
代码：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class BigInteger {
private:
vector<int> digits; // 低位在前存储
public:
BigInteger() { digits.push_back(0); }
BigInteger(int num) {
if (num == 0) {
digits.push_back(0);
}
while (num > 0) {
digits.push_back(num % 10);
num /= 10;
}
}
// 高精度乘法
BigInteger operator*(const BigInteger& other) const {
BigInteger 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) {
int product = result.digits[i + j] + digits[i] *
(j < other.digits.size() ? other.digits[j] : 0) + carry;
carry = product / 10;
result.digits[i + j] = product % 10;
}
}
// 去除前导零
while (result.digits.size() > 1 && result.digits.back() == 0) {
result.digits.pop_back();
}
return result;
}
friend ostream& operator<<(ostream& os, const BigInteger& num) {
for (int i = num.digits.size() - 1; i >= 0; --i) {
os << num.digits[i];
}
return os;
}
};
vector<int> findOptimalDecomposition(int n) {
vector<int> result;
if (n <= 4) {
result.push_back(n - 1);
result.push_back(1);
sort(result.begin(), result.end());
return result;
}
int sum = 0;
for (int i = 2; ; i++) {
if (sum + i > n) break;
sum += i;
result.push_back(i);
}
int remaining = n - sum;
for (int i = result.size() - 1; i >= 0 && remaining > 0; i--) {
result[i]++;
remaining--;
}
if (remaining > 0) {
result.back() += remaining;
}
return result;
}
int main() {
int n;
cin >> n;
vector<int> decomposition = findOptimalDecomposition(n);
BigInteger product(1);
// 输出分解方案
for (size_t i = 0; i < decomposition.size(); ++i) {
if (i != 0) cout << " ";
cout << decomposition[i];
}
cout << endl;
// 计算乘积
for (int num : decomposition) {
product = product * BigInteger(num);
}
cout << product << endl;
return 0;
}
代码解析
- BigInteger类（不想说了：
-
实现高精度整数存储和乘法运算
-
支持从普通整数构造
-
重载输出运算符便于打印结果
- 分解算法：
-
findOptimalDecomposition函数找到最优分解方案 -
从2开始连续累加自然数，直到不能再加
-
处理剩余的数，从高位开始分配
- 主程序：
-
读取输入的正整数n
-
获取最优分解方案
-
计算这些数的乘积（使用高精度乘法）
-
输出分解方案和最大乘积
关键点
-
分解策略：连续自然数分解+剩余分配策略
-
高精度计算：处理大数乘积问题
-
边界处理：特殊处理n≤4的情况
-
输出格式：按要求输出分解方案和乘积结果
T11 A7880.天使的起誓
代码：
#include <iostream>
#include <string>
using namespace std;
int findBoxNumber(int n, const string& m) {
int remainder = 0;
for (char digit : m) {
remainder = (remainder * 10 + (digit - '0')) % n;
}
return remainder == 0 ? n : remainder;
}
int main() {
int n;
string m;
cin >> n >> m;
int boxNumber = findBoxNumber(n, m);
cout << boxNumber << endl;
return 0;
}
代码解析
- 高精度取模算法：
-
使用字符串存储大数m
-
逐位处理，模拟手工除法取余的过程
-
对于每一位数字，更新当前的余数
- 特殊情况处理：
-
当余数为0时，表示宝盒编号为n（因为编号从1开始）
-
否则余数即为宝盒编号
- 输入输出：
-
读取n和m（m作为字符串读取）
-
计算并输出结果
关键点
-
大数处理：使用字符串存储超过普通整数范围的m
-
高效取模：O(len(m))时间复杂度，适用于极大数
-
边界条件：正确处理m是n的倍数的情况
-
内存优化：不需要存储整个大数，逐位处理节省内存
T12 A7881.麦森数 （ 泰森数
代码：
#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>
using namespace std;
const int DIGITS = 500; // 需要计算的位数
const int BASE = 1000000000; // 基数，每位存储9位数字
const int BASE_DIGITS = 9;
class BigInt {
private:
vector<int> digits;
public:
BigInt() { digits.push_back(0); }
BigInt(int num) {
if (num == 0) {
digits.push_back(0);
}
while (num > 0) {
digits.push_back(num % BASE);
num /= BASE;
}
}
// 快速幂算法计算2^P
static BigInt powerOfTwo(int P) {
BigInt result(1);
for (int i = 0; i < P; ++i) {
result = result + result; // 相当于乘以2
if (result.digits.size() > DIGITS / BASE_DIGITS + 1) {
result.digits.resize(DIGITS / BASE_DIGITS + 1);
}
}
return result;
}
// 大数加法
BigInt operator+(const BigInt& other) const {
BigInt result;
result.digits.clear();
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];
carry = sum / BASE;
result.digits.push_back(sum % BASE);
}
return result;
}
// 减去1
BigInt minusOne() const {
BigInt result = *this;
int i = 0;
while (i < result.digits.size() && result.digits[i] == 0) {
result.digits[i] = BASE - 1;
i++;
}
if (i < result.digits.size()) {
result.digits[i]--;
} else {
result.digits.push_back(-1); // 处理特殊情况
}
// 去除前导零
while (result.digits.size() > 1 && result.digits.back() == 0) {
result.digits.pop_back();
}
return result;
}
// 计算位数
int calculateDigits() const {
if (digits.empty()) return 0;
int d = (digits.size() - 1) * BASE_DIGITS;
int n = digits.back();
while (n > 0) {
d++;
n /= 10;
}
return d;
}
// 输出最后500位
void printLast500Digits() const {
vector<int> lastDigits(DIGITS, 0);
int pos = 0;
// 从最低位开始处理
for (int i = 0; i < digits.size() && pos < DIGITS; ++i) {
int num = digits[i];
for (int j = 0; j < BASE_DIGITS && pos < DIGITS; ++j) {
lastDigits[pos++] = num % 10;
num /= 10;
}
}
// 输出10行，每行50位
for (int i = 0; i < 10; ++i) {
for (int j = 0; j < 50; ++j) {
int idx = DIGITS - 1 - (i * 50 + j);
if (idx >= 0) {
cout << lastDigits[idx];
} else {
cout << '0';
}
}
cout << endl;
}
}
};
int main() {
int P;
cin >> P;
// 计算位数：log10(2^P) = P * log10(2)
int digits = static_cast<int>(P * log10(2)) + 1;
cout << digits << endl;
// 计算2^P - 1的最后500位
BigInt result = BigInt::powerOfTwo(P).minusOne();
result.printLast500Digits();
return 0;
}
代码解析
- BigInt类：
-
使用
vector<int>存储大数，每个元素存储9位数字 -
实现快速幂算法计算
-
实现大数加法和大数减1操作
- 位数计算：
-
使用数学公式：位数 =
-
避免直接计算超大数的位数
- 最后500位计算：
-
在快速幂计算过程中限制位数
-
特殊处理减法操作
-
格式化输出最后500位数字
- 输入输出：
-
读取输入的P值
-
输出位数和最后500位数字
关键点
-
高效计算：使用快速幂算法优化的计算
-
内存管理：只保留必要的位数（最后500位）
-
数学优化：用对数计算总位数，避免直接处理超大数
-
输出格式化：按要求格式输出最后500位数字
有帮助，赞一个