【新手上路】洛谷算法1-1：模拟与高精度(高精度部分)
纵浪大化中，不喜亦不惧
文章目录
- [P1601 A+B Problem（高精）](https://www.luogu.com.cn/problem/P1601)
- [P1303 A*B Problem](https://www.luogu.com.cn/problem/P1303)
- [P1009 [NOIP1998 普及组] 阶乘之和](https://www.luogu.com.cn/problem/P1009)
- [P1591 阶乘数码](https://www.luogu.com.cn/problem/P1591)
- [P1249 最大乘积](https://www.luogu.com.cn/problem/P1249)
- [P1045 [NOIP 2003 普及组] 麦森数](https://www.luogu.com.cn/problem/P1045#submit)
- 总结：
P1601 A+B Problem（高精）
- 模板题不必赘述
代码如下：
#include <bits/stdc++.h>
using namespace std;
string big_add(string a1, string a2)
{
const int l = 505; // 其实502足够了
int l1 = a1.size(), l2 = a2.size(), num1[l] = {0}, num2[l] = {0};
string ans = "";
// 倒序剥离数位
for (int i = 0; i < l1; ++i) num1[i] = a1[l1 - 1 - i] - '0';
for (int i = 0; i < l2; ++i) num2[i] = a2[l2 - 1 - i] - '0';
// 对齐数位
int lmax = l1 > l2 ? l1 : l2;
// 高精加法核心
for (int i = 0; i < lmax; ++i)
{
num1[i] += num2[i];
num1[i + 1] += num1[i] / 10;
num1[i] %= 10;
}
if (num1[lmax]) lmax++;
// 转换成字符串
for (int i = lmax - 1; i >= 0; --i)
{
ans += num1[i] + '0';
}
return ans;
}
int main()
{
string a1, a2;
cin >> a1 >> a2;
cout << big_add(a1, a2);
}
P1303 A*B Problem
- 同样是模板题
代码如下：
#include <bits/stdc++.h>
using namespace std;
string big_mul(string a1, string a2)
{
if (a1 == "0" || a2 == "0")
return "0";
const int l = 4005;
int l1 = a1.size(), l2 = a2.size(), num1[l] = {0}, num2[l] = {0}, carry[l] = {0};
string ans = "";
// 倒序剥离数位
for (int i = 1; i <= l1; ++i)
num1[i] = a1[l1 - i] - '0';
for (int i = 1; i <= l2; ++i)
num2[i] = a2[l2 - i] - '0';
// 核心
for (int i = 1; i <= l1; ++i)
{
for (int j = 1; j <= l2; ++j)
{
carry[i + j - 1] += num1[i] * num2[j];
}
}
// 统一处理进位
for (int i = 1; i <= l1 + l2; ++i)
{
carry[i + 1] += carry[i] / 10;
carry[i] %= 10;
}
// 转换
if (carry[l1 + l2])
ans += carry[l1 + l2] + '0';
for (int i = l1 + l2 - 1; i >= 1; --i)
{
ans += carry[i] + '0';
}
return ans;
}
int main()
{
string a1, a2;
cin >> a1 >> a2;
cout << big_mul(a1, a2);
}
P1009 [NOIP1998 普及组] 阶乘之和
- 大数加法和乘法的结合运用
代码如下：
#include <bits/stdc++.h>
using namespace std;
string big_add(string a1, string a2)
{
const int l = 5005;
int l1 = a1.size(), l2 = a2.size(), num1[l] = {0}, num2[l] = {0};
string ans = "";
for (int i = 0; i < l1; ++i)
num1[i] = a1[l1 - 1 - i] - '0';
for (int i = 0; i < l2; ++i)
num2[i] = a2[l2 - 1 - i] - '0';
int lmax = l1 > l2 ? l1 : l2;
for (int i = 0; i < lmax; ++i)
{
num1[i] += num2[i];
num1[i + 1] += num1[i] / 10;
num1[i] %= 10;
}
if (num1[lmax])
lmax++;
for (int i = lmax - 1; i >= 0; --i)
{
ans += num1[i] + '0';
}
return ans;
}
string big_mul(string a1, string a2)
{
// if (a1 == "0" || a2 == "0")return "0";
const int l = 5005;
int l1 = a1.size(), l2 = a2.size(), num1[l] = {0}, num2[l] = {0}, carry[l] = {0};
string ans = "";
// 倒序剥离数位
for (int i = 1; i <= l1; ++i)
num1[i] = a1[l1 - i] - '0';
for (int i = 1; i <= l2; ++i)
num2[i] = a2[l2 - i] - '0';
// 核心
for (int i = 1; i <= l1; ++i)
{
for (int j = 1; j <= l2; ++j)
{
carry[i + j - 1] += num1[i] * num2[j];
}
}
// 统一处理进位
for (int i = 1; i <= l1 + l2; ++i)
{
carry[i + 1] += carry[i] / 10;
carry[i] %= 10;
}
// 转换
if (carry[l1 + l2])
ans += carry[l1 + l2] + '0';
for (int i = l1 + l2 - 1; i >= 1; --i)
{
ans += carry[i] + '0';
}
return ans;
}
int main()
{
int n;
cin >> n;
string sum_mul, sum_add = "0";
for (int i = 1; i <= n; ++i)
{
sum_mul = "1";
for (int j = 1; j <= i; ++j)
{
sum_mul = big_mul(sum_mul, to_string(j));
}
sum_add = big_add(sum_add, sum_mul);
}
cout << sum_add;
}
P1591 阶乘数码
- 模拟加高精度
代码如下：
#include <bits/stdc++.h>
using namespace std;
string big_mul(string a1, string a2)
{
// if (a1 == "0" || a2 == "0")return "0";
const int l = 5005;
int l1 = a1.size(), l2 = a2.size(), num1[l] = {0}, num2[l] = {0}, carry[l] = {0};
string ans = "";
// 倒序剥离数位
for (int i = 1; i <= l1; ++i)
num1[i] = a1[l1 - i] - '0';
for (int i = 1; i <= l2; ++i)
num2[i] = a2[l2 - i] - '0';
// 核心
for (int i = 1; i <= l1; ++i)
{
for (int j = 1; j <= l2; ++j)
{
carry[i + j - 1] += num1[i] * num2[j];
}
}
// 统一处理进位
for (int i = 1; i <= l1 + l2; ++i)
{
carry[i + 1] += carry[i] / 10;
carry[i] %= 10;
}
// 转换
if (carry[l1 + l2])
ans += carry[l1 + l2] + '0';
for (int i = l1 + l2 - 1; i >= 1; --i)
{
ans += carry[i] + '0';
}
return ans;
}
int main()
{
int t;
cin >> t;
while (t--)
{
int n;
char s;
cin >> n >> s;
string sum = "1";
for (int i = 1; i <= n; ++i)
{
sum = big_mul(sum, to_string(i));
}
int l = sum.size(), cnt = 0;
for (int i = 0; i < l; ++i)
{
if (sum[i] == s)
cnt++;
}
cout << cnt << endl;
}
}
P1249 最大乘积
- 贪心策略是：从2开始的连续自然数，剩下的余数k，加在倒数第k位置，没有倒数第k位就加在2上，数学严谨证明过于复杂，贪心类题目不适合证明
代码如下：
#include <bits/stdc++.h>
using namespace std;
string big_mul(string a1, string a2) // 高精度乘法
{
const int l = 5005;
int l1 = a1.size(), l2 = a2.size(), n1[l] = {0}, n2[l] = {0}, carry[l] = {0};
string ans = "";
for (int i = 1; i <= l1; ++i) // 从1开始
n1[i] = a1[l1 - i] - '0'; // 减‘0’
for (int i = 1; i <= l2; ++i)
n2[i] = a2[l2 - i] - '0';
for (int i = 1; i <= l1; ++i)
{
for (int j = 1; j <= l2; ++j)
{
carry[i + j - 1] += n1[i] * n2[j]; // i+j-1错 ； +=
}
}
for (int i = 1; i <= l1 + l2; ++i)
{
carry[i + 1] += carry[i] / 10; // +=
carry[i] %= 10;
}
if (carry[l1 + l2])
ans += carry[l1 + l2] + '0';
for (int i = l1 + l2 - 1; i >= 1; --i) // 从l1+l2-1开始
{
ans += carry[i] + '0';
}
return ans;
}
int main()
{
int n, k;
cin >> n;
k = n;
vector<int> ans;
for (int i = 2;; ++i) //规律是从2开始的连续自然数剩下的余数k加在倒数第k位置没有倒数第k位就加在2上
{
k -= i;
if (k < 0)
{
k += i;
break;
}
ans.push_back(i);
}
int l = ans.size();
if (l >= k)
{
ans[l - k] += k;
}
else
{
ans[0] += k;
}
sort(ans.begin(), ans.end());
string res = "1";
for (int i = 0; i < l; ++i)
{
cout << ans[i] << " ";
res = big_mul(to_string(ans[i]), res);
}
cout << endl
<< res;
}
P1045 [NOIP 2003 普及组] 麦森数
- 雄关漫道真如铁
代码如下：
// #include <bits/stdc++.h>
// using namespace std;
// const int l = 1100005;
// int n1[l], n2[l], carry[l];
// string big_mul(string a1, string a2)
// {
// int l1 = a1.size(), l2 = a2.size();
// memset(n1, 0, sizeof n1);
// memset(n2, 0, sizeof n2);
// memset(carry, 0, sizeof carry);
// string ans = "";
// for (int i = 1; i <= l1; ++i)
// n1[i] = a1[l1 - i] - '0';
// for (int i = 1; i <= l2; ++i)
// n2[i] = a2[l2 - i] - '0';
// for (int i = 1; i <= l1; ++i)
// {
// for (int j = 1; j <= l2; ++j)
// {
// carry[i + j - 1] += n1[i] * n2[j];
// }
// }
// for (int i = 1; i <= l1 + l2; ++i)
// {
// carry[i + 1] += carry[i] / 10;
// carry[i] %= 10;
// }
// if (carry[l1 + l2])
// ans += carry[l1 + l2] + '0';
// for (int i = l1 + l2 - 1; i >= 1; --i)
// {
// ans += carry[i] + '0';
// }
// return ans;
// }
// string quick_pow(int base, int exp)
// {
// string ans = "1", Base = to_string(base);
// while (exp)
// {
// if (exp & 1)
// {
// ans = big_mul(ans, Base);
// }
// Base = big_mul(Base, Base);
// exp >>= 1;
// }
// return ans;
// }
// string big_sub(string a1, string a2)
// {
// int l1 = a1.size(), l2 = a2.size();
// memset(n1, 0, sizeof n1);
// memset(n2, 0, sizeof n2);
// string ans = "";
// for (int i = 0; i < l1; ++i)
// n1[i] = a1[l1 - 1 - i] - '0';
// for (int i = 0; i < l2; ++i)
// n2[i] = a2[l2 - 1 - i] - '0';
// int lmax = l1 > l2 ? l1 : l2;
// for (int i = 0; i < lmax; ++i)
// {
// n1[i] -= n2[i];
// if (n1[i] < 0)
// {
// n1[i] += 10;
// n1[i + 1]--;
// }
// }
// while (lmax > 0 && !n1[--lmax])
// ; // 重点：去除前导0
// lmax++;
// for (int i = lmax - 1; i >= 0; --i)
// {
// ans += n1[i] + '0';
// }
// return ans;
// }
// int main()
// {
// int exp;
// cin >> exp;
// string ans = big_sub(quick_pow(2, exp), "1");
// cout << ans.size() << endl;
// if (ans.size() >= 500)
// {
// ans = ans.substr(ans.size() - 500, 500);
// }
// else
// {
// ans = string(500 - ans.size(), '0') + ans;
// }
// for (int i = 0; i < 500; ++i)
// {
// cout << ans[i];
// if (i + 1 % 50 == 0)
// cout << endl;
// }
// } 以上是错误的，问题是会爆栈且高精乘O(n^2)时间复杂度过高
#include <bits/stdc++.h>
using namespace std;
const int mod = 500; // 只保留最后500位数字
// 高精度乘法（仅处理最后500位）
vector<int> big_mul(vector<int> a1, vector<int> a2) {
vector<int> carry(mod, 0); // 存储中间结果（逆序存储，索引0是个位）
// 核心乘法计算（优化版）
for(int i = 0; i < mod; ++i) {
if(a1[i] == 0) continue; // 乘数当前位为0时跳过，优化效率
// 只计算会影响最后500位的乘积
for(int j = 0; j < mod && i+j < mod; ++j) {
carry[i+j] += a1[i] * a2[j]; // 累加到对应位置
}
}
// 进位处理（从低位到高位）
for(int i = 0; i < mod-1; ++i) {
carry[i+1] += carry[i] / 10; // 将进位传递到下一位
carry[i] %= 10; // 保证当前位值在0-9之间
}
carry[mod-1] %= 10; // 单独处理最高位的进位（确保不超过9）
return carry; // 返回结果仍为逆序存储（索引0是结果的个位）
}
// 快速幂算法计算2^exp（最后500位）
vector<int> q_pow(int exp) {
vector<int> base(mod, 0), res(mod, 0);
base[0] = 2; // 初始化基数为2（逆序存储：2的个位是2）
res[0] = 1; // 初始化结果为1（逆序存储：1的个位是1）
while(exp) {
if(exp & 1)
res = big_mul(res, base); // 当指数为奇数时累乘结果
base = big_mul(base, base); // 基数平方（每次运算都保留500位）
exp >>= 1; // 指数右移（相当于除以2）
}
return res; // 返回的res是逆序存储的2^exp的最后500位
}
// 大数减1操作（处理逆序存储的500位数字）
vector<int> big_subone(vector<int> a1) {
a1[0] -= 1; // 直接对个位减1
// 处理借位（只需要处理到倒数第二位，防止越界）
for(int i = 0; i < mod-1; ++i) {
if(a1[i] < 0) { // 需要借位的情况
a1[i] += 10; // 当前位补10
a1[i+1] -= 1; // 下一位减1
}
}
return a1; // 返回逆序存储的减1后的结果
}
int main() {
int p;
cin >> p;
// 计算位数公式：floor(p*log10(2)) + 1
cout << (int)(p * log10(2)) + 1 << endl;
// 计算2^p的最后500位（逆序存储），然后减1
vector<int> ans = big_subone(q_pow(p));
// 转换为正常顺序的字符串
string res;
for(int i = mod-1; i >= 0; --i) { // 从最高位开始转换
res += ans[i] + '0'; // 将数字转换为字符
}
// 格式化输出最后500位
for(int i = 0; i < 10; ++i) { // 输出10行
// 每行截取50个字符：第0行取0-49，第1行取50-99，依此类推
cout << res.substr(i*50, 50) << endl;
}
return 0;
}
总结：
在二进制流转的娑婆世界里，算法犹如渡河之筏。当世人畏惧大数运算的浩瀚相，常生退转之心，却不知三千烦恼本是三千菩提。高精度算法看似要直面数位如恒河沙的困局，实则是破除法相执着的修行法门。
编程者当学须菩提解空第一的智慧。进位借位间流转的，何尝不是缘起性空的示现？每一个字符的迭代正如禅门公案中的机锋，乘法竖式里藏着华严十玄门的重重无尽。初习者莫畏数位浩瀚，须知十方虚空尚在吾人本性中，况此五百位乎？
那些看似枯燥的循环嵌套，恰似达摩面壁的九年功夫。当乘方运算在快速幂中层层开显，方知"一即一切，一切即一"的妙谛。进位链上的波动，恰如因果相续的缘起法，当下的每次位运算都在编织数字宇宙的因陀罗网。
莫道此中无真意，万行代码汇菩提。编程之道本无难易，畏惧心才是最大的魔障。当知高精度算法不过是镜中月影，照见的实是吾人处理复杂问题的般若智慧。念念分明地写就每一行进位处理，终将在二进制河流中照见五蕴皆空。