洛谷 P1303 A*B Problem 题解与拓展

2020-03-13   90 次阅读


一看到题目,什么?一题普及-的题目也要发题解?
这一点都不格局,也不高雅,十分蒟蒻
其实只是先写个题解作为模板

解析

数的大小超过10的2000次方,明显要用高精度(看到题解里还有人说什么FTT)
string然后开数组声明一对初始变量完成初始化

思路

先看个简单的例子
25*25
可以分解为(20+5)X25 = 20X25+5X25
同样的每个乘法都可以分解成其中一个数每个位与另一个数的所有位进行相乘,然后将结果加到特定位
从25的低位开始运算

  1. 5*5=25,需要进2位,保留5加到第1位,将进位数2加到第二位(25)

  2. 随后5*2=10,0+2=2,只需要进1位(25)

  3. 将1加入到第三位中(125)

  4. 随后高位2*5=10,需要进1位,这里注意因为2是十位,因此要将0加到结果的十位而不是个位上,将1加到第三位(225)

  5. 2*2=4,将4加到第三位(625)
    求得结果625

从上述运算过程来看,我们需要设置两个进位数,一个用于存储位间乘法运算的进位数(本人称为乘法进位数),一个用于存储结果加上当前结果数的进位数(通常都为1或0,本人称为加法进位数)

思路确定下来后,代码其实就很好写了,寡人修行不透,因此只写出了O(n2)的解法

代码

#include <iostream>
using namespace std;
int main()
{
    int mulR;           //存储位与位间乘法运算结果
    int result[5000];   //存储最终结果(2000位乘以2000位大概结果在4000位左右,为了保险开了5000的数组
    int upperM=0;       //mul,乘法进位数
    int upperA=0;       //add,加法进位数
    int addIn = 0;      //需要加到最终结果位中的当前结果
    int pos =0;         //插入位置
    std::string c,d;    //存放两个数的字符串
    std::cin>>c>>d;
    if(c=="0"||d=="0")   //考虑到会等于0的情况,避免麻烦先筛掉
        {
            std::cout<<0;
            return 0;
        }
    for(int i=c.length()-1;i>=0;i--)   //从第一个数的低位开始(注意字符串的话是从末尾往前是从低到高)
    {
        int mula=c[i]-'0';              //获取位数整型形式便于计算
        for(int j=d.length()-1;j>=0;j--)
        {
            pos = d.length()-1-j+c.length()-1-i;  //计算插入位置
            int mulb=d[j]-'0';         
            mulR=mula*mulb;              //位与位相乘
            upperM=mulR/10;              //计算乘法进位数
            addIn=mulR%10;		 //计算当前结果
            result[pos]+=(upperA+addIn); //将最终结果的指定位加上当前结果与上一次的加法进位数(上一次运算的进位)
            result[pos+1]+=upperM;       //将乘法进位数加到下一位
            upperA=result[pos]/10;       //计算加法进位数
            result[pos]=result[pos]%10;  
        }
        result[pos+1]+=upperA;            //在完成一个位的运算后要将剩余的进位进到下一个位上
        upperA=0;
    }
    for(int i=pos;i>=0;i--)
        std::cout<<result[i];             //输出结果
    return 0;
}

结果与改进

代码放上去结果就5个测试点,一下就AC了,我才想起来我好像没考虑负数。那这个数据集确实有点水(水人说水)

不行啊,所以最终我又将代码添加了带有负数的情况
判断符号是基础,但是还有一个地方要注意的是,如果使用字符串读取的话,负号也是在字符串当中的,因此按照上述代码的话负号也会一同运算,其实只要根据两数符号的情况设立计算终止点即可,修改代码如下

#include <iostream>
using namespace std;
int main()
{
    int mulR;
    int result[5000];
    int upperM=0;
    int upperA=0;
    int addIn = 0;
    int pos =0;
    int sign=0;
    int Cend,Dend;     //两个数的计算终止点
    std::string c,d;
    std::cin>>c>>d;
    if(c=="0"||d=="0")
        {
            std::cout<<0;
            return 0;
        }
        if(c[0]=='-') 
    {
        sign++;
        Cend=1;       //假如第一个数为负数,那么计算终止点就为1(符号不能一起拿进去运算啊)
    }
    else Cend=0;
    if(d[0]=='-')
    {
        sign++;
        Dend=1; 	//同上
    }
    else Dend=0;
        for(int i=c.length()-1;i>=Cend;i--)
    {
        int mula=c[i]-'0';
        for(int j=d.length()-1;j>=Dend;j--)
        {
            pos = d.length()-1-j+c.length()-1-i;
            int mulb=d[j]-'0';
            mulR=mula*mulb;
            upperM=mulR/10;
            addIn=mulR%10;
            result[pos]+=(upperA+addIn);
            result[pos+1]+=upperM;
            upperA=result[pos]/10;
            result[pos]=result[pos]%10;
        }
        result[pos+1]+=upperA;
        upperA=0;
    }
    if(sign%2!=0)     //倘若sign变量模2为0,则说明没有负数或是两个数相乘,否则输出符号
        std::cout<<"-";
    for(int i=pos;i>=0;i--)
        std::cout<<result[i];
    return 0;
}

总结

你瞧瞧一题水题给我整的,没啥好总结的,就是高精度。肥仔快乐撸代码

Q.E.D.

知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议