-1

我正在解决SPOJ 上的FAST MULTIPLICATION。我的解决方案如下所示：

#include<bits/stdc++.h>
using namespace std;
int max(int a,int b)
{
    if(a>b) return a;
    return b;
}
long karatsuba_multiply(int x,int y)
{
    if(x<10 or y<10) return x*y;
    int n=max(to_string(x).length(),to_string(y).length());
    int m=(int)ceil(n/2.0);
    long p=(long)pow(10,m);
    long a=(long)(floor(x/p));
    long b=x%p;
    long c=(long)(y/p);
    long d=y%p;
    long ac=karatsuba_multiply(a,c);
    long bd=karatsuba_multiply(b,d);
    long adbc=karatsuba_multiply(a+b,c+d)-ac-bd;
    return (long)(pow(10*1,2*m)*ac+pow(10*1,m)*adbc+bd);
}
int main()
{
    int a,b,t;
    cin>>t;
    while(t--)
    {
        cin>>a>>b;
        cout<<karatsuba_multiply(a,b)<<endl;
    }
    return 0;
}

此代码在编码块 IDE 以及其他 IDE 上给出正确的输出。但是这个解决方案在 SPOJ 上被标记为错误的。谁能告诉我我做错了什么？

4

2 回答 2

1

C++ 最初只支持 unsigned long long 整数的最大长度约为 1.8e19。

根据问题，答案最多可以射到 1e100000000，这要大得多。

解决这个问题的方法是：

  • 使用字符串存储整数并使用对字符串的操作进行乘法运算。你可以查看这篇文章
  • 使用C++ 升压库。该库支持超过 1e19 限制的整数运算。

另一种方法是使用其他支持大于 64 位整数的语言（如 Python）或使用 Java 中的 BigInteger 类

于 2020-12-05T19:43:54.663 回答
0

从问题描述：

Input

n [the number of multiplications <= 1000]

l1 l2 [numbers to multiply (at most 10000 decimal digits each)]

Text grouped in [ ] does not appear in the input file.

具有 10000 个十进制数字的数字太大而无法int放入int. 您需要为输入使用不同的类型并执行乘法运算。没有内置类型可以存储这么大的整数。

于 2020-12-05T12:23:38.803 回答