算法·高精度

高精度算法

• 分为四则运算加减乘除

适用条件

• 都高精度了，肯定时long long都会爆的情况——一般与阶乘有关

注意事项

• 用数组模拟位运算，最后在一起考虑进位
  • 注意res[i+1]+=res[i]/10; 是"+="不是=
• 两数相加，相乘数组的新长度会变，要正确计算！
  • 加法：len=max(lena,lenb)+1
  • 乘法：len=lena+lenb+1
• 位运算的公式
  • 加法：a[i] += b[i];
  • 乘法：res[i+j-1]+=a[i]*b[j];模拟乘法运算，一个数字乘以行的情况
• 对于阶乘：
  • 最好是定义一个类bigInt，便于组织代码
  • for(int i=2;i<=n;i++){ x*i }利用循环模拟，不建议递归

加法模板

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
string stra, strb;
int a[5009];
int b[5009];
void solve() {cin >> stra >> strb;int lena = stra.size(), lenb = strb.size();for (int i = lena-1; i >= 0; i--) {a[lena - i] = stra[i]-'0';}/*for (int i = lena; i >= 1; i--) {cout << a[i];}cout << endl;*/for (int i = lenb - 1; i >= 0; i--) {b[lenb - i] = strb[i]-'0';}/*for (int i = lenb; i >= 1; i--) {cout << b[i];}cout << endl;*/int len = max(lena, lenb) + 2;for (int i = 1; i <= len; i++) {a[i] += b[i];}//for (int i = len; i >= 1; i--) {//    cout << a[i] << " ";//}//cout << endl;for (int i = 1; i <= len; i++) {a[i + 1] += a[i] / 10;a[i] %= 10;}/*for (int i = len; i >= 1; i--) {cout << a[i] << " ";}*/for (; a[len]==0&&len>0;len--);if (len <=1) {cout << 0;return;}for (int i = len; i >= 1; i--) {cout << a[i];}
}

乘法模板

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
string stra, strb;
int a[5009];
int b[5009];
int res[5009];
void solve() {cin >> stra >> strb;int lena = stra.size(), lenb = strb.size();for (int i = lena-1; i >= 0; i--) {a[lena - i] = stra[i]-'0';}for (int i = lenb - 1; i >= 0; i--) {b[lenb - i] = strb[i]-'0';}int len = lena + lenb + 2;for (int i = 1; i <= lena; i++) {for (int j = 1; j <= lenb; j++) {res[i + j - 1] += a[i] * b[j];}}/*for (int i = 1; i <= 10; i++) {cout << res[i] << " ";}cout << endl;*/for (int i = 1; i <= len; i++) {res[i + 1] += res[i] / 10;res[i] %= 10;}/*for (int i = 1; i <= 10; i++) {cout << res[i] << " ";}*//*for (int i = len; i >= 1; i--) {cout << a[i] << " ";}*/for (; res[len]==0&&len>0;len--);if (len <1) {cout << 0;return;}for (int i = len; i >= 1; i--) {cout << res[i];}
}

阶乘模板

using namespace std;
using ll = long long;
int t,n,a,ct;
class bigInt {
public://构造一个类，避免重复开辟新空间int a[5009];int len;bigInt() {memset(a, 0, sizeof(a));a[1] = 1;len = 1;}void operator*(int b) {for (int i = 1; i <= len; i++) {a[i] *= b;}len += b/10+1;//扩容不是固定的+2！！！for (int i = 1; i <= len; i++) {a[i + 1] += a[i] / 10;a[i] %= 10;}for (; a[len]==0; len--);}void print() {for (int i = len; i >= 1; i--) {cout << a[i];}}
};
bigInt number;
void solve() {cin >> t;while (t--) {cin >> n >> a;if (n == 0) {//特判0!=1(也可以不特判)cout << (a == 1 ? 1 : 0); continue;}for (int i = 2; i <= n; i++) {number* i;//原地对number不断发生阶乘运算//你也可以定义=运算符，但是我懒}number.print();cout << endl;}
}

以下均为例题

阶乘数码

题目描述

求 $n!$ 中某个数码出现的次数。

输入格式

第一行为 $t(t\le 10)$，表示数据组数。接下来 $t$ 行，每行一个正整数 $n(n\le 1000)$ 和数码 $a$。

输出格式

对于每组数据，输出一个整数，表示 $n!$ 中 $a$ 出现的次数。

样例 #1

样例输入 #1

2
5 2
7 0

样例输出 #1

1
2

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int t,n,a,ct;
class bigInt {
public:int a[5009];int len;bigInt() {memset(a, 0, sizeof(a));a[1] = 1;len = 1;}void operator*(int b) {for (int i = 1; i <= len; i++) {a[i] *= b;}len += b/10+1;//扩容不是固定的+2！！！for (int i = 1; i <= len; i++) {a[i + 1] += a[i] / 10;a[i] %= 10;}for (; a[len]==0; len--);}void print() {for (int i = len; i >= 1; i--) {cout << a[i];}}
};
bigInt number;
void solve() {cin >> t;while (t--) {cin >> n >> a;if (n == 0) {cout << (a == 1 ? 1 : 0); continue;}memset(number.a, 0, sizeof(number.a));number.a[1] = 1;number.len = 1;ct = 0;//初始化for (int i = 2; i <= n; i++) {number* i;//不断发生变换}/*number.print();cout << endl;*/for (int i = 1; i <= number.len; i++) {if (number.a[i] == a) {ct++;}}cout << ct<<endl;}
}
signed main() {std::ios::sync_with_stdio(false);std::cin.tie(0); std::cout.tie(0);solve();return 0;
}