高精度乘法

这篇具有很好参考价值的文章主要介绍了高精度乘法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、算法描述

高精度加减法讨论的是两个大整数之间的运算。

而这里高精度乘除法讨论的是一个大整数和一个小整数之间的关系。

算法思路:

  • 还是模拟小学的乘法列竖式,只不过此时不太一样,原本的列竖式是一位一位的乘,这里需要改变一下思路。

  • 这里直接把小整数当成一个数,所乘的数直接当成进位参与运算即可。

  • 每次进位t += A[i] * b,然后将当前位数上的数(t % 10)加入答案数组,然后让t成为下一位的进位,t /= 10

  • 因为是乘法,所以会有可能超过很多位,我们需要把他们都加入答案数组而且不要忘了一位一位的加。

  • 如果一个很大的数乘 \(0\) 的话,那么会产生很多前导 \(0\) ,我们也需要处理一下。

经过优化之后代码如下:

vector<int> mul(vector<int> &A, int b)
{
    vector<int> C;
    int t = 0;
    
    for (int i = 0; i < A.size(); ++i)
    {
        t += b * A[i];
        
        C.push_back(t % 10);
        
        t /= 10;
    }
    while (t)   C.push_back(t % 10), t /= 10;
    while (C.size() > 1 && C.back() == 0)   C.pop_back();
    
    return C;
}

二、题目描述

给定两个非负整数(不含前导 \(0\)\(A\)\(B\),请你计算 \(A×B\) 的值。

输入格式

共两行,第一行包含整数 \(A\),第二行包含整数 \(B\)

输出格式

共一行,包含 \(A × B\) 的值。

数据范围

\(1≤A的长度≤100000,\)
\(0≤B≤10000\)文章来源地址https://www.toymoban.com/news/detail-710943.html

输入样例:

2
3 

输出样例:

6 

三、题目来源

AcWing算法基础课-793.高精度乘法

四、源代码

#include <iostream>
#include <vector>

using namespace std;

const int N = 100010;

vector<int> mul(vector<int> &A, int b)
{
    vector<int> C;
    int t = 0;
    
    for (int i = 0; i < A.size(); ++i)
    {
        t += A[i] * b;
        
        C.push_back(t % 10);
        
        t /= 10;
    }
    while (t)   C.push_back(t % 10), t /= 10;
    while (C.size() > 1 && C.back() == 0)   C.pop_back();
    
    return C;
}

int main()
{
    string a;
    int b;
    cin >> a >> b;
    
    vector<int> A;
    for (int i = a.size() - 1; i >= 0; --i) A.push_back(a[i] - '0');
    
    vector<int> C = mul(A, b);
    for (int i = C.size() - 1; i >= 0; --i) cout << C[i];
    
    return 0;
}

到了这里,关于高精度乘法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 高精度乘法

    高精度加减法讨论的是两个大整数之间的运算。 而这里高精度乘除法讨论的是一个大整数和一个小整数之间的关系。 算法思路: 还是模拟小学的乘法列竖式,只不过此时不太一样,原本的列竖式是一位一位的乘,这里需要改变一下思路。 这里直接把小整数当成一个数,所乘

    2024年02月08日
    浏览(49)
  • 高精度乘法模板(fft)

     正常高精度复杂度是o(n^2),fft复杂度o(nlogn)

    2024年02月10日
    浏览(41)
  • Acwing793. 高精度乘法

    AcWing 793. 高精度乘法 A x b 和 A x B 的模版(大数相加、大数相乘通用模板)

    2024年02月10日
    浏览(35)
  • C语言 加减乘除模 的 高精度计算 (超详细)

    目录 高精度加法 高精度乘法 高精度减法          高精度除法 高精度模法   高精度计算 是模拟算法的一种,通过字符串和整型数组的使用,将加减乘除的竖式运算 模拟 出来,达到计算的目的。其步骤大致分为:一,将字符串数据存到整型数组中,二,模拟算法,不同的

    2023年04月24日
    浏览(38)
  • 高精度加法,减法,乘法,除法(上)(C语言)

    前言 本篇内容介绍加法和减法,如果想看乘法和除法就点这里-高精度乘法,除法 加,减,乘,除这些运算我们自然信手捏来,就拿加法来说,我们要用c语言编程算a+b的和,只需让sum = a+b即可,可是这是局限的,我们都知道int的表示的最大值为2147483647(32位和64位机器)。但

    2024年02月03日
    浏览(40)
  • 高精度加法,减法,乘法,除法(下)(C语言)

    前言 上一篇博客我们分享了高精度加法,减法,这一期我将为大家讲解高精度乘法和高精度除法。那让我们开始吧! 对加法和减法感兴趣的话就点我 让我们想想我们平时做数学时遇见乘法是怎么做的。以下图为例。 高精度乘法也是这样的一个思路,首先我们先把a和b的值储存

    2024年02月04日
    浏览(65)
  • (基础算法)高精度加法,高精度减法

    什么叫做高精度加法呢?包括接下来的高精度减法,高精度乘法与除法都是同一个道理。正常来讲的话加减乘除,四则运算的数字都是整数,也就是需要在int的范围之内,但当这个操作数变得非常\\\"大\\\"的时候( 其实就是一个字符串,比方说有一个数是20位,如果用整数视角来

    2024年02月01日
    浏览(55)
  • 通过类实现矩阵加减法、乘法、转置(C++))

    定义一个二维方阵类 matrix 通过重载二元运算符“+”、“-”、“*”和一元运算符“~”, 来实现矩阵加、矩阵减、矩阵乘以及矩阵转置。 1.由于矩阵的行与列都是未知的,首先需要通过 动态分配内存 实现创建任意大小的矩阵,由于类中默认的构造函数无法满足我们的需求,

    2024年02月06日
    浏览(56)
  • 算法笔记——高精度算法(附源码)

    📖作者介绍:22级树莓人(计算机专业),热爱编程<目前在c++阶段, 因为最近参加新星计划算法赛道(白佬),所以加快了脚步,果然急迫感会增加动力 ——目标Windows,MySQL,Qt,数据结构与算法,Linux,多线程,会持续分享学习成果和小项目的 📖作者主页:热爱编程的

    2023年04月08日
    浏览(61)
  • 【算法】模拟,高精度

      P1601 A+B Problem(高精) - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 思路就是模拟,值得注意的就是要用字符串类型输入。存进自己的int数组时要倒着存,因为如果是正着存的话,进位会有点trouble。 时间复杂度O(max(m,n))    P1303 A*B Problem - 洛谷 | 计算机科学教育新生态 (lu

    2024年02月09日
    浏览(49)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包