算法·高精度

高精度算法

• 分为四则运算加减乘除

适用条件

• 都高精度了，肯定时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;
}