算法·高精度

高精度算法

  • 分为四则运算加减乘除

适用条件

  • 都高精度了,肯定时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 ! n! n! 中某个数码出现的次数。

输入格式

第一行为 t ( t ≤ 10 ) t(t \leq 10) t(t10),表示数据组数。接下来 t t t 行,每行一个正整数 n ( n ≤ 1000 ) n(n \leq 1000) n(n1000) 和数码 a a a

输出格式

对于每组数据,输出一个整数,表示 n ! n! n! a a 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;
}

相关推荐

  1. 精度算法

    2024-07-10 22:42:05       23 阅读
  2. 精度模拟算法

    2024-07-10 22:42:05       14 阅读
  3. 算法·精度

    2024-07-10 22:42:05       7 阅读
  4. 基础算法-精度加法 基础算法-精度加法

    2024-07-10 22:42:05       29 阅读

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-07-10 22:42:05       3 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-10 22:42:05       3 阅读
  3. 在Django里面运行非项目文件

    2024-07-10 22:42:05       2 阅读
  4. Python语言-面向对象

    2024-07-10 22:42:05       2 阅读

热门阅读

  1. 闲聊C++与面向对象思想

    2024-07-10 22:42:05       7 阅读
  2. 路由器中 RIB 与 FIB 的区别

    2024-07-10 22:42:05       13 阅读
  3. 生成日志系统和监控

    2024-07-10 22:42:05       11 阅读
  4. Apache Spark详解

    2024-07-10 22:42:05       8 阅读
  5. qt opencv 应用举例

    2024-07-10 22:42:05       8 阅读
  6. Pytorch中分类回归常用的损失和优化器

    2024-07-10 22:42:05       8 阅读
  7. 【Rust】Cargo介绍

    2024-07-10 22:42:05       8 阅读
  8. 搭建Spring Cloud项目思路

    2024-07-10 22:42:05       8 阅读
  9. C语言从头学32——字符串数组

    2024-07-10 22:42:05       8 阅读
  10. 7. 有奖猜谜

    2024-07-10 22:42:05       7 阅读
  11. 关于redis的运维面试题-2

    2024-07-10 22:42:05       7 阅读
  12. socketserver和WSGI服务端实现教程

    2024-07-10 22:42:05       10 阅读
  13. 数组常用的方法

    2024-07-10 22:42:05       7 阅读
  14. 设计模式实现思路介绍

    2024-07-10 22:42:05       10 阅读