大数乘法__牛客网

xxining

考虑连续进位的问题

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param s string字符串 第一个整数
     * @param t string字符串 第二个整数
     * @return string字符串
     */
    string solve(string s, string t) {
        // write code here
        if(s.empty()||t.empty()) return "0";
        int m = s.size(), n=t.size();
        string res(m+n,'0');
        for(int i=m-1;i>=0;--i){
            for(int j=n-1;j>=0;--j){
                int temp = (s[i]-'0')*(t[j]-'0') + res[i+j+1]-'0';
                res[i+j+1] = temp%10 +'0';
                int add = temp/10;
                int k = 0;
                while(add!=0 && i+j-k>=0){
                    int temp2 = res[i+j-k]-'0'+add;
                    res[i+j-k] = temp2 %10 +'0';
                    add = temp2/10;
                    ++k;
                }
            }
        }
        for(int i=0;i<m+n;++i){
            if(res[i]!='0')
                return res.substr(i,m+n-i+1);
        }
        return "0";
    }
};

发表于 2021-12-22 22:47:18 回复(0)

C++

昨天的明天的牛友

class Solution 
{
public:
    // 实现s*t
    string mul(string s, char t)
    {
        int num = t - '0', len = s.length(), carry = 0;
        string ans = "";
        for (int i = len - 1; i >= 0; --i)
        {
            // 乘法的结果
            int a = s[i] - '0';
            int b = a * num;
            // 求和
            int c = b + carry;
            // 进位
            carry = c / 10;
            // 余数
            c %= 10;
            // 添加结果
            ans = ans + to_string(c);
        }
        // 如果余数不为零
        if (carry != 0)
        {
            ans = ans + to_string(carry);
        }
        // 字符串逆转
        reverse(ans.begin(), ans.end());
        return ans;
    }
    
    // 实现s+num*t，即在t后面补num个零
    string add(string s, string t, int num)
    {
        for (int i = 0; i < num; ++i)
        {
            t = t + "0";
        }
        // s+t
        string ans = "";
        // 进位
        int carry = 0;
        int s_len = s.length(), t_len = t.length();
        // 双指针
        int i = s_len - 1, j = t_len - 1;
        // 遍历
        while (i >= 0 || j >= 0)
        {
            int a = (i < 0) ? 0 : s[i] - '0';
            int b = (j < 0) ? 0 : t[j] - '0';
            // 向前移动，负数也没有关系
            --i;
            --j;
            // 和
            int sum = a + b + carry;
            // 进位
            carry = sum / 10;
            // 余数
            sum %= 10;
            // 添加结果
            ans = ans + to_string(sum);
        }
        // 如果还有进位
        if (carry != 0)
        {
            ans = ans + to_string(carry);
        }
        // 字符串逆转
        reverse(ans.begin(), ans.end());
        return ans;
    }
    
    string solve(string s, string t) 
    {
        if (s == "0" || t == "0")
        {
            return "0";
        }
        string ans = "";
        int len = t.length();
        // 用s去乘以t的每一位
        for (int i = len - 1; i >= 0; --i)
        {
            // 使用s乘以t的第i位
            string temp_mul = mul(s, t[i]);
            // 累加
            ans = add(ans, temp_mul, len - i - 1);
        }
        return ans;
    }
};

运行时间超过百分之零点几，空间超过个位数，大佬们提下改进意见呗，谢谢了。

发表于 2021-09-28 10:54:20 回复(0)

靑い石

不就是加法吗

import java.util.*;


public class Solution {
    /**
    描述
以字符串的形式读入两个数字，编写一个函数计算它们的乘积，以字符串形式返回。
（字符串长度不大于10000，保证字符串仅由'0'~'9'这10种字符组成）
示例1
输入：
"11","99"
复制
返回值：
"1089"
复制
说明：
11*99=1089  
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param s string字符串 第一个整数
     * @param t string字符串 第二个整数
     * @return string字符串
     */
   public String solve(String s, String t) {
        if ("".equals(s) && "".equals(t)) {
            return "0";
        }

        String result = "0";
        int otherZero = 0;

        for (int j = t.length() - 1; j >= 0; j--) {
            String toAdd = muti(s, t.charAt(j) - '0', otherZero);
            result = add(result, toAdd);
            otherZero++;
        }
        return result;
    }

    public String add(String s, String t) {
        if ("0".equals(t)) {
            return "0";
        } else if ("1".equals(t)) {
            return s;
        }
        int inc = 0;
        StringBuilder sb = new StringBuilder("");
        int i = s.length() - 1;
        int j = t.length() - 1;

        while (i >= 0 || j >= 0 || inc == 1) {
            int left = i >= 0 ? s.charAt(i) - '0' : 0;
            int right = j >= 0 ? t.charAt(j) - '0' : 0;

            int sum = left + right;

            if (inc == 1) {
                sum += 1;
                inc = 0;
            }

            if (sum >= 10) {
                sum = sum % 10;
                inc = 1;
            }

            i--;
            j--;

            sb.append(sum);
        }
        sb.reverse();
        return sb.toString();
    }

    public String muti(String str, int muti, int lastZero) {
        if (muti == 0) {
            return "";
        }
        StringBuilder result = new StringBuilder(str);
        for (int i = 0; i < muti - 1; i++) {
            result = new StringBuilder(add(result.toString(), str));
        }
        for (int i = 0; i < lastZero; i++) {
            result.append("0");
        }
        return result.toString();
    }
}

发表于 2021-06-24 15:51:29 回复(0)

Java

惠灵顿靖

import java.util.*;
public class Solution {
    public String solve (String s, String t) {
        //将字符串转化为数组形式
        int len1=s.length(),len2=t.length();
        int[] a1=new int[len1];
        for(int i=0;i<len1;i++)a1[i]=s.charAt(i)-'0';
        int[] a2=new int[len2];
        for(int i=0;i<len2;i++)a2[i]=t.charAt(i)-'0';
        // 开辟结果数组，结果长度至多为 lenOne + lenTwo
        int[] tmp=new int[len1+len2];
        // 开始计算，先不考虑进位,每次结果存在result[i + j + 1]位置
        // 为什么是i + j + 1? 
        // 因为结果数组计算处理高位在数组左，低位在数组右。
        //i+j+1实际上是往低位存，这样后面进位处理才正确
        for(int i=0;i<len1;i++){
            for(int j=0;j<len2;j++){
                tmp[i+j+1]+=a1[i]*a2[j];
            }
        }
        //进位
        int carry=0;
        for(int i=len1+len2-1;i>=0;i--){
            tmp[i]=tmp[i]+carry;
            carry=tmp[i]/10;
            tmp[i]=tmp[i]%10;
        }
        // 转为String，需要无视前置0
        StringBuilder res=new StringBuilder();
        int cur=0;
        while(cur<len1+len2&&tmp[cur]==0)cur++;
        //添加
        for(int i=cur;i<len1+len2;i++)res.append(tmp[i]);
        //如果最终res长度为0,则代表输入类似"0" "0"的用例，结果应该输出“0”
        return res.length()==0?"0":res.toString();
    }
}

发表于 2021-04-14 22:32:45 回复(0)

木析

a*b分解为b的每一位去乘以a，然后将相乘的结果相加

（ps.写的时候还忘了竖式咋相乘，用草稿纸写了下才知道……我可太菜了）

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param s string字符串 第一个整数
     * @param t string字符串 第二个整数
     * @return string字符串
     */
    string solve(string s, string t) {
        string curZero="";
        int lenT=t.size();
        string res="";
        for(int i=lenT-1;i>=0;i--) {
            string cur=(getMul(s,t[i]-'0')+curZero);
            Add(res,cur);
            curZero+="0";
        }
        return res;
    }
    void Add(string &res,string x) {
        //将res和x表示的数字相加，返回结果的字符串形式
        string s="";
        int len1=res.size()-1;
        int len2=x.size()-1;
        int ex=0;
        while(len1>=0 || len2>=0) {
            int num=ex;
            if(len1<0) {
                num+=(x[len2]-'0');
                len2--;
            } else if(len2<0) {
                num+=(res[len1]-'0');
                len1--;
            } else{
                num+=(res[len1]-'0');
                num+=(x[len2]-'0');
                len2--;
                len1--;
            }
            s+=('0'+num%10);
            ex=num/=10;
        }
        if(ex!=0) {
            s+=('0'+ex);
        }
        reverse(s);
        res="";
        //去掉前置0
        int i=0;
        while(i<s.size() && s[i]=='0')
            i++;
        if(i==s.size()) {
            res="0";
        } else{
            while(i<s.size()) {
                res+=s[i];
                i++;
            }
        }
    }
    void reverse(string &m) {
        for(int i=0,j=m.size()-1;i<j;i++,j--) {
            char ch=m[i];
            m[i]=m[j];
            m[j]=ch;
        }
    }
    string getMul(string s,int x) {
        string m="";
        int len=s.size();
        int ex=0;//进位
        for(int i=len-1;i>=0;i--) {
            int cur=s[i]-'0';
            int mul=cur*x+ex;
            m+=((mul%10)+'0');
            ex=mul/10;
        }
        if(ex!=0) {
            m+=(ex+'0');
        }
        reverse(m);
        return m;
    }
};

发表于 2021-04-07 11:48:33 回复(0)

野地里的百合花

牛客网真是沙雕，测试用例经常给的一知半解，你个位数是前面还是后面？

发表于 2021-01-06 19:59:28 回复(2)

C++

仲夏夜之梦626

//参考其他大佬的思路写的
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param s string字符串 第一个整数
     * @param t string字符串 第二个整数
     * @return string字符串
     */
    string solve(string s, string t) {
        // write code here
        if(s=="0"||t=="0") return "0";
        string res(s.size()+t.size(),'0');
        int jinwei;
        for(int i=s.size()-1;i>=0;--i){
            jinwei=0;
            for(int j=t.size()-1;j>=0;--j){
                int tmp=(s[i]-'0')*(t[j]-'0')+res[i+j+1]-'0'+jinwei;
                jinwei=tmp/10;
                res[i+j+1]=tmp%10+'0';
            }
            if(jinwei) res[i]=jinwei+'0';
        }
        int i=0;
        while(i<res.size()&&res[i]=='0') ++i;
        return res.substr(i);
    }
};

发表于 2022-03-27 10:23:07 回复(2)

C++

南七技校

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param s string字符串 第一个整数
     * @param t string字符串 第二个整数
     * @return string字符串
     */
    string solve(string s, string t) {
        // write code here
        reverse(s.begin(), s.end());
        reverse(t.begin(), t.end());
        vector<int> num1, num2;
        for (const auto& c : s) num1.push_back(c - '0');
        for (const auto& c : t) num2.push_back(c - '0');
        vector<int> ans(num1.size() + num2.size() + 1, 0);
        for (int i = 0; i < num1.size(); i++) {
            for (int j = 0; j < num2.size(); j++) {
                ans[i + j] += num1[i] * num2[j];
            }
        }
        string ret;
        for (int i = 0; i < num1.size() + num2.size(); i++) {
            if (ans[i] <= 0) break;
            if (ans[i] > 10) {
                ans[i + 1] += ans[i] / 10;
                ans[i] = ans[i] % 10;
            }
            ret.push_back(ans[i] + '0');
        }
        reverse(ret.begin(), ret.end());
        if (ret.empty()) return "0";
        return ret;
    }
};

来看看我丑陋的代码

发表于 2021-07-18 00:54:36 回复(2)

WYACAC

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param s string字符串 第一个整数
     * @param t string字符串 第二个整数
     * @return string字符串
     */
   private  static  final  int MAXN = 20010;
        private Complex[] x1 = new Complex[MAXN];
        private Complex[] x2 = new Complex[MAXN];
        private int[] sum = new int[MAXN];
        StringBuffer sb = new StringBuffer();
        private static final  double pi = Math.acos(-1.0);
        private static class Complex{
                private double x;
                private double y;
                public Complex(double x,double y){
                        this.x = x;
                        this.y = y;
                }
                public Complex add(Complex o1,Complex o2){
                        return new Complex(o1.x+o2.x,o1.y+o2.y);
                }
                public Complex subtract(Complex o1,Complex o2){
                        return new Complex(o1.x-o2.x,o1.y-o2.y);
                }
                public Complex multiply(Complex o1,Complex o2){
                        return new Complex(o1.x*o2.x-o1.y*o2.y,o1.y*o2.x+o1.x*o2.y);
                }
        }
        public void change(Complex[] y,int len){
                int i,j,k;
                for(i=1,j=len/2;i<len-1;i++){
                        if(i<j){
                                Complex tem =y[i];
                                y[i] = y[j];
                                y[j] = tem;
                        }
                        k = len/2;
                        while (j>=k){
                                j-=k;
                                k/=2;
                        }
                        if(j<k) j+=k;
                }
        }
        public void fft(Complex[] y,int len,int on){
                change(y,len);
                for(int h=2;h<=len;h<<=1){
                        Complex wn = new Complex(Math.cos(-on*2*pi/h),Math.sin(-on*2*pi/h));
                        for(int j=0;j<len;j+=h){
                                Complex w = new Complex(1,0);
                                for(int k=j;k<j+h/2;k++){
                                        Complex u = y[k];
                                        Complex t = w.multiply(w,y[k+h/2]);
                                        y[k] = u.add(u,t);
                                        y[k+h/2] = u.subtract(u,t);
                                        w = w.multiply(w,wn);
                                }
                        }
                }
            if(on==-1){
                        for(int i=0;i<len;i++)
                                y[i].x/=len;
                }
        }
        public String solve (String s, String t) {
                int len1 = s.length();
                int len2 = t.length();
                int len=1;
                while (len<len1*2||len<len2*2)
                        len<<=1;
                for(int i=0;i<len1;i++)
                        x1[i] = new Complex(s.charAt(len1-i-1)-'0',0);
                for(int i=len1;i<len;i++)
                        x1[i] = new Complex(0,0);
                for(int i=0;i<len2;i++)
                        x2[i] = new Complex(t.charAt(len2-i-1)-'0',0);
                for(int i=len2;i<len;i++)
                        x2[i] = new Complex(0,0);
                fft(x1,len,1);
                fft(x2,len,1);
                for(int i=0;i<len;i++)
                        x1[i] = x1[i].multiply(x1[i],x2[i]);
                fft(x1,len,-1);
                for(int i=0;i<len;i++)
                        sum[i] = (int)(x1[i].x+0.5);
                for(int i=0;i<len;i++){
                        sum[i+1]+=sum[i]/10;
                        sum[i]%=10;
                }
                len = len1+len2-1;
                while (sum[len]<=0&&len>0)
                        len--;
                for(int i=len;i>=0;i--)
                        sb.append(sum[i]);
                return sb.toString();
        }
}

发表于 2021-03-22 22:20:36 回复(0)

Java

iMi丶

import java.util.*;


public class Solution {
    public static String solve (String s, String t) {
        // 数字数组，高位在数组左，低位在数组右，处理时需注意
        int[] arrOne = new int[s.length()];
        for(int i = 0 ; i < s.length() ; i++){
            arrOne[i] = s.charAt(i) - '0';
        }
        int[] arrTwo = new int[t.length()];
        for(int i = 0 ; i < t.length() ; i++){
            arrTwo[i] = t.charAt(i) - '0';
        }

        return getRes(arrOne,arrTwo);
    }

    public static String getRes(int[] arrOne,int[] arrTwo){
        int lenOne = arrOne.length;
        int lenTwo = arrTwo.length;

        // 开辟结果数组，结果长度至多为 lenOne + lenTwo
        int[] result = new int[lenOne + lenTwo];

        // 开始计算，先不考虑进位,每次结果存在result[i + j + 1]位置
        // 为什么是i + j + 1? 
        // 因为结果数组计算处理高位在数组左，低位在数组右。i+j+1实际上是往低位存，这样后面进位处理才正确
        for(int i =  0; i< lenOne ; i++){
            for(int j = 0 ; j < lenTwo ; j++){
                // !!!这里是i + j + 1这样最后的进位才能正确计算
                result[i + j + 1] += arrOne[i] * arrTwo[j];
            }
        }

        // 计算该位进位和结果数,从最低位(数组末尾)开始向前计算
        int carry = 0;
        for(int i = result.length - 1 ; i >= 0 ; i--){
            int sum = carry + result[i];
            result[i] = sum % 10;
            carry = sum / 10;
        }

        // 转为String，需要无视前置0,如果最终builder长度为0,则代表输入类似"0" "0"的用例，结果应该输出“0”
        StringBuilder builder = new StringBuilder();
        int curPos = 0;
        while(curPos < result.length && result[curPos] == 0){
            curPos++;
        }
        for(int i = curPos ; i < result.length ; i++){
            builder.append(result[i]);
        }
        return builder.length() != 0 ? builder.toString() : "0";
    }
}

编辑于 2020-11-28 21:22:46 回复(0)

唐氏综合征

大数乘法：实际上就是用代码模拟了一下乘法的手动计算过程

1. 如果 s 和 t 任意一方为0. 那么乘积结果肯定为 0

2. 由于 s * t 的结果最长长度只会≤ m+n, 因此初始化一个数组用于存储计算结果

3. 开始从最低位开始计算，p1 代表当前的高位下标，p2 代表当前的低位下标

4. 在计算当前的低位时，一定要检查当前低位下标对应的值是否存在，如果存在，则说明它是上一轮计算的高位值，由于当前轮是上一轮的进一位，因此需要加上

5. 当内层循环一轮时，外层循环的当前值需要进一位，此时的累加应该乘以10再跟上一轮循环的结果相加，因此需要错位累加，程序上的提现就是由于 i -1 了，所以错位累加时，高位仍然是 p1 = i + j , 低位也仍然是 i +j + 1, 因此 result[p1] 和 result[p2]的计算仍然准确。

6. 这道题的关键点在于 i = 2, j =1 时和 i = 1, j = 2 位数是一样的，这就好比一个数的个位乘以一个数的十位和一个数的十位乘以一个数的个位，它们在最终结果的位数都是一样的，高位都在第三位，低位都在第二位，因此 result[p1] += sum / 10 仍然是有效的。

代码:

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串 第一个整数
     * @param t string字符串 第二个整数
     * @return string字符串
     */
    public String solve (String s, String t) {
        // 如果有一个数为0，乘积就是0
        if (s.equals("0") || t.equals("0")) {
            return "0";
        }

        int m = s.length();
        int n = t.length();

        // 用于存储乘积的结果
        int[] result = new int[m + n];

        // 从最低位到最高位逐位相乘
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                int mul = (s.charAt(i) - '0') * (t.charAt(j) - '0');
                int p1 = i + j;
                int p2 = i + j + 1;
                int sum = mul + result[p2];

                result[p2] = sum % 10;
                result[p1] += sum / 10;
            }
        }

        // 将结果数组转换为字符串
        StringBuilder sb = new StringBuilder();
        for (int num : result) {
            // 跳过前导零
            if (!(sb.length() == 0 && num == 0)) {
                sb.append(num);
            }
        }

        return sb.length() == 0 ? "0" : sb.toString();
    }
}

发表于 2024-05-31 12:41:46 回复(0)

Python3

大大大🍍

class Solution:
    def solve(self , s: str, t: str) -> str:
        # write code here
        if s ==''&nbs***bsp;t =='':
            return ''
        return str(int(s)*int(t))

发表于 2022-12-08 15:56:23 回复(0)

C++

算法小屁孩

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param s string字符串 第一个整数
     * @param t string字符串 第二个整数
     * @return string字符串
     */
    string solve(string s, string t) {
        if(s=="0" || t=="0"){
            return "0";
        }
        string ans(s.length()+t.length(), '0');
        int carry=0;
        for(int i=0;i<s.length();i++){
            for(int j=0;j<t.length();j++){
                char tmp = ans[ans.length()-1-j-i];
                ans[ans.length()-1-i-j] = ((s[s.length()-1-i]-'0')*(t[t.length()-1-j]-'0')+tmp-'0'+carry)%10+'0';
                carry = ((s[s.length()-1-i]-'0')*(t[t.length()-1-j]-'0')+tmp-'0'+carry)/10;
            }
            ans[ans.length()-1-i-t.length()] = carry+'0';
            carry = 0;
        }
        int mark = 0;
        while(mark<ans.length()-1 && ans[mark]=='0'){
            mark++;
        }
        return ans.substr(mark);
    }
};

发表于 2021-09-07 23:27:39 回复(0)

Python 3

VincentLau~

class Solution:
    def solve(self , s , t ):
        # write code here
        def multiply(a, b):
            b = int(b)
            res, carry = "", 0
            for c in a:
                tmp = int(c) * b + carry
                res += str(tmp % 10)
                carry = tmp // 10
            if carry:
                res += str(carry)
            return res
        s, t = s[::-1], t[::-1]
        if len(s) < len(t): n1, n2 = t, s
        else: n1, n2 = s, t
        res = []
        for c in n2:
            tmp = multiply(n1, c)
            res.append(int(tmp[::-1]))
        ans = 0
        for num in res[::-1]:
            ans = 10*ans + num
        return str(ans)

发表于 2021-08-14 18:22:51 回复(0)

Python 3

Stephenling

class Solution:
def solve(self , s , t ):
# write code here
return str(int(s)*int(t))

发表于 2021-08-10 22:15:14 回复(0)

C/C++

牛客69143547号

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param s string字符串 第一个整数
     * @param t string字符串 第二个整数
     * @return string字符串
     */
    string solve(string s, string t) {
        // write code here
        int n1=s.size();int n2=t.size();
        string res(n1+n2,'0');
        for(int i=n1-1;i>=0;i--)
        {
            for(int j=n2-1;j>=0;j--)
            {
                int temp=res[i+j+1]-'0'+(s[i]-'0')*(t[j]-'0');
                res[i+j+1]=temp%10+'0';
                res[i+j]+=temp/10;
            }
        }
        for(int i=0;i<n1+n2;i++)
        {
            if(res[i]!='0')
                return res.substr(i);
        }
        return "0";
    }
};

发表于 2021-03-06 08:59:04 回复(0)

游骑兵PXZ

使用BigInteger不香吗？

    public static String solve(String s, String t) {
        if ("".equals(s) || "".equals(t)) {
            return "";
        }
        BigInteger b1 = new BigInteger(s);
        BigInteger b2 = new BigInteger(t);
        BigInteger res = b1.multiply(b2);
        return String.valueOf(res);
    }

发表于 2020-11-22 20:34:46 回复(5)

牛客341319853号

class Solution:
    def solve(self , s: str, t: str) -> str:
        # write code here
        s_val = eval(s)
        t_val = eval(t)
        result = s_val*t_val

        return str(result)

eval可以返回真实值，比使用int更好

发表于 2024-11-06 14:58:57 回复(0)

ಥ雨霖铃ಥ

我是菜逼，只会用api

import java.util.*;
import java.math.BigDecimal;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串 第一个整数
     * @param t string字符串 第二个整数
     * @return string字符串
     */
    public String solve (String s, String t) {
        // write code here
        return new BigDecimal(t).multiply(new BigDecimal(s)).toPlainString();
    }
}

发表于 2024-11-01 17:06:04 回复(0)

C

一只小马喽

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param s string字符串 第一个整数
 * @param t string字符串 第二个整数
 * @return string字符串
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void addStr(char* a, char* b,int addlen,int multlen,int k){
    addlen = addlen-k;
    int i,j,tmp;
    tmp = 0;
    for(i=addlen-1,j=multlen-1;i>=0,j>=0;i--,j--){
        tmp = (a[i] -'0') + (b[j]-'0') + tmp;
        if (tmp>=10) {
            a[i] = tmp%10 + '0';
            tmp = 1;
        }else if (tmp<10) {
            a[i] = tmp + '0';
            tmp = 0;
        }
    }
    if (tmp > 0) {
        a[j] = tmp +a[j];
    }

    return ;
}
char* multiStr(char x, char* y ){
    int ylen = strlen(y);
    int tmp = 0;
    char* multmp = (char*)calloc(ylen + 1 , 1);
    for (int i = 0; i< (ylen+1); i++) {
        multmp[i]='0';
    }
    int multmplen = ylen+1;
    for (int i = ylen - 1; i>=0; i--) {
        tmp =tmp + (x-'0')*(y[i]-'0');
        multmp[multmplen-1] = tmp % 10 + '0';
        tmp = tmp / 10;
        multmplen--;
    }
    if (tmp > 0) {
        multmp[0] = multmp[0]+tmp;
    }
    // for (int i = 0; i< (ylen+1); i++) {
    //     printf("%c",multmp[i]);
    // }
    // printf("\n");
    // while (*multmp == '0') {
    //     multmp++;
    // }
    return multmp;
}
char* solve(char* s, char* t ) {
    // write code here
    int slen = strlen(s);
    int tlen = strlen(t);
    char* multmp = (char*)calloc(tlen + 1 , 1);
    char* addtmp = (char*)calloc(slen + tlen + 2 , 1);
    for (int i = 0; i< (tlen+1); i++) {
        multmp[i]='0';
    }
    for (int i = 0; i< (slen + tlen + 2); i++) {
        addtmp[i]='0';
    }
    for (int i = slen-1 ; i>=0; i--) {
            multmp = multiStr(s[i], t);
            addStr(addtmp, multmp,slen + tlen + 2,tlen + 1,slen-i-1);
    }

    int n=0;
    while (*addtmp == '0') {
        addtmp++;
        n++;
    }
    if (n == slen + tlen + 2) {
        addtmp--;
    }
    // if (!addtmp) {
    //     return &addtmp[1];
    // }
    return addtmp;
}

发表于 2024-10-16 16:20:47 回复(0)

大数乘法

输入

输出

说明

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题