@[Rickysun](/user/824205) 跟乘法列竖式的原理差不多啊
by DFs_YYDS @ 2024-02-13 11:20:32
@[DFs_YYDS](/user/1119406) 原理知道,代码不会写
by __Rickysun__ @ 2024-02-13 11:23:36
那你就背代码呗
by Istruggle @ 2024-02-13 11:24:19
@[Rickysun](/user/824205) 稍等,正在修改80分代码
by DFs_YYDS @ 2024-02-13 11:24:22
@[Rickysun](/user/824205) 艹,没特判0
by DFs_YYDS @ 2024-02-13 11:26:04
@[Rickysun](/user/824205) 把每一位乘之后的数用数组存起来,最后进位
by DFs_YYDS @ 2024-02-13 11:27:18
@[Rickysun](/user/824205) lz目前目标?
如果是pj那么背代码就行了,反正也就那么点东西,很好理解的
by heyx0201 @ 2024-02-13 11:42:46
```cpp
#include<iostream>
#include<cstring>
using namespace std;
string a1,b1;
int a[2010],b[2010],ans[4010],t,s;
int main(){
cin >> a1 >> b1;
int len1 = a1.size();
int len2 = b1.size();
int lenc =len1+len2;
for(int i = 0;i<len1;i++)
a[i] = a1[len1-i-1] - '0';
for(int i = 0;i<len2;i++)
b[i] = b1[len2-i-1] - '0';
for(int i=0;i<len1;i++){
for(int j=0;j<len2;j++){
ans[i+j]+=a[i]*b[j];
}
}
for(int i=0;i<lenc;i++){
if(ans[i]>9){
ans[i+1]+=ans[i]/10;
ans[i]%=10;
}
}
t=lenc-1;
while(t>0&&!ans[t]){
t--;
}
for(int i=t;i>=0;i--){
cout<<ans[i];
}
return 0;
}
```
@[Rickysun](/user/824205)
by rnfmabj5114 @ 2024-02-13 11:43:21
楼上正解,完全能够通过本题
但是这里提供一些优化,比如说一个从常数上提供极大优化的方案,即“压位高精度”,将原来的十进制竖式计算改成百进制之类,假设压 $x$ 位,高精度的位数为 $n$ ,则其时间复杂度应该能够压缩到 $O((n\div lgx)\times(n\div lgx))$
当然这只是在常数上的简单优化,在数据特别大的时候就不管用了
这个时候我们就可以参考 oiwiki:
在数据规模大的时候,建议使用 Karatsuba 乘法(速度可以达到 $O(n^{log_23})$)或者基于多项式的乘法,使用快速傅里叶变换和快速数论变换等优化使其复杂度达到 $O(n log n)$
by masonxiong @ 2024-02-14 12:48:55