高精度算法

基础模板：

(411条消息) 高精度加法_会笑的小熊的博客-CSDN博客

(411条消息) 高精度乘法_会笑的小熊的博客-CSDN博客

(411条消息) 高精度减法_会笑的小熊的博客-CSDN博客

目录

P1601 A+B Problem（高精）

P1303 A*B Problem

P1009 [NOIP1998 普及组] 阶乘之和

P1591 阶乘数码 

P1249 最大乘积

---

P1601 A+B Problem（高精）

vector版

vector<int> add(vector<int> &A, vector<int> &B)
{vector<int> C;int t = 0;for (int i = 0; i < A.size() || i < B.size(); i++){if (i < A.size())t += A[i];if (i < B.size())t += B[i];C.pb(t % 10);t /= 10;}if (t)C.pb(t);return C;
}inline void solve()
{string a, b;cin >> a >> b;vector<int> A, B;for (int i = a.size() - 1; i >= 0; i--)A.pb(a[i] - '0');for (int i = b.size() - 1; i >= 0; i--)B.pb(b[i] - '0');auto C = add(A, B);for (int i = C.size() - 1; i >= 0; i--)cout << C[i];
}

数组版 

const int N = 1e5 + 10;
int A[N], B[N], C[N]; // 将每位数字保存在数组中
inline void solve()
{string a, b;cin >> a >> b;int s1 = a.size(), s2 = b.size();// 将第一个乘数逆序保存在数组A[1],A[2]....中for (int i = 0; i < a.size(); i++)A[s1 - i] = a[i] - '0';for (int i = 0; i < b.size(); i++)B[s2 - i] = b[i] - '0';for (int i = 1; i <= s1 || i <= s2; i++){if (i <= s1)C[i - 1] += A[i]; // 将每一次求的值相加if (i <= s2)C[i - 1] += B[i];C[i] += C[i - 1] / 10; // 将十位数字加到下一位C[i - 1] %= 10;        // 将个位数字保存在当前位}int s = s1 + s2;while (C[s] == 0 && s > 0) // 若最高位为0 则位数减一s--;if (s == 0)cout << 0 << endl;else{for (int i = s; i >= 0; i--) // 倒叙输出 由高位到低位cout << C[i];}
}

P1303 A*B Problem

const int N = 1e5 + 10;
int A[N], B[N], C[1000010]; // 将每位数字保存在数组中
inline void solve()
{string a, b;cin >> a >> b;int s1 = a.size(), s2 = b.size();// 将第一个乘数逆序保存在数组A[1],A[2]....中for (int i = 0; i < a.size(); i++)A[s1 - i] = a[i] - '0';for (int i = 0; i < b.size(); i++)B[s2 - i] = b[i] - '0';for (int i = 1; i <= s1; i++){for (int j = 1; j <= s2; j++){C[i + j - 1] += A[i] * B[j];   // 将每一次求的值相加C[i + j] += C[i + j - 1] / 10; // 将十位数字加到下一位C[i + j - 1] %= 10;            // 将个位数字保存在当前位}}int s = s1 + s2;while (C[s] == 0 && s > 0) // 若最高位为0 则位数减一s--;if (s == 0)cout << 0 << endl;else{for (int i = s; i >= 1; i--) // 倒叙输出 由高位到低位cout << C[i];}
}

P1009 [NOIP1998 普及组] 阶乘之和

int A[1010] = {0}, B[1010] = {0};
inline void solve()
{int n;cin >> n;A[0] = B[0] = 1;for (int i = 2; i <= n; i++){for (int j = 0; j < 100; j++)B[j] *= i;   //预处理阶乘for (int j = 0; j < 100; j++){B[j + 1] += B[j] / 10;B[j] %= 10;}for (int j = 0; j < 100; j++){A[j] += B[j];A[j + 1] += A[j] / 10;A[j] %= 10;}}int i = 100;while (i >= 0 && A[i] == 0)i--;for (int j = i; j >= 0; j--)cout << A[j];
}

P1591 阶乘数码 

vector<int> mul(vector<int> &A, int b)
{vector<int> C;int t = 0;for (int i = 0; i < A.size() || t; i++){if (i < A.size())t += A[i] * b;C.pb(t % 10);t /= 10;}while (C.size() > 1 && C.back() == 0)C.pop_back();return C;
}inline void solve()
{int n, a;cin >> n >> a;vector<int> A;int cnt = 0;A.pb(1);for (int i = 2; i <= n; i++)A = mul(A, i);for (int i = 0; i < A.size(); i++)if (A[i] == a)cnt++;cout << cnt << endl;
}

P1249 最大乘积

LuoGu P1249 最大乘积（数论 + 前缀和） | 码农家园 (codenong.com)

int d[10010];vector<int> mul(vector<int> &A, int b)
{vector<int> C;int t = 0;for (int i = 0; i < A.size() || t; i++){if (i < A.size())t += A[i] * b;C.pb(t % 10);t /= 10;}while (C.size() > 1 && C.back() == 0)C.pop_back();return C;
}void process(int n)
{int s = 0;for (int i = 2; i <= n; i++){s += i;d[i] = true;if (s > n){if (s - n == 1){d[2] = false;d[i] = false;d[i + 1] = true;break;}d[s - n] = false;break;}}
}inline void solve()
{int n;cin >> n;process(n);for (int i = 0; i < 10010; i++){if (d[i])cout << i << ' ';}cout << endl;vector<int> A;A.pb(1);for (int i = 0; i < 10010; i++){if (d[i])A = mul(A, i);}for (int i = A.size() - 1; i >= 0; i--)cout << A[i];
}