3 条题解
-
0
本题可以用快速傅里叶变换FFT来解决,代码如下。
#include <bits/stdc++.h> using namespace std; const double PI=acos(-1.0); void FFT(vector<complex<double>>& a,bool invert){ int n=a.size(); if (n==1) return; vector<complex<double>>a0(n/2),a1(n/2); for (int i=0;2*i<n;i++){ a0[i]=a[2*i]; a1[i]=a[2*i+1]; } FFT(a0,invert); FFT(a1,invert); double angle=2*PI/n*(invert?-1:1); complex<double>w(1),wn(cos(angle),sin(angle)); for (int i=0;2*i<n;i++){ a[i]=a0[i]+w*a1[i]; a[i+n/2]=a0[i]-w*a1[i]; if (invert){ a[i]/=2; a[i+n/2]/=2; } w*=wn; } } vector<int> operator*(const vector<int>&a,const vector<int>&b){ vector<complex<double>>fa(a.begin(),a.end()),fb(b.begin(),b.end()); int n=1; while (n<a.size()+b.size()) n<<=1; fa.resize(n); fb.resize(n); FFT(fa,false); FFT(fb,false); for (int i=0;i<n;i++) fa[i]*=fb[i]; FFT(fa,true); vector<int>result(n); for (int i=0;i<n;i++) result[i]=int(round(fa[i].real())); return result; } string multiplyStrings(const string& num1, const string& num2) { if (num1 == "0" || num2 == "0") return "0"; vector<int> a, b; for (int i = num1.size() - 1; i >= 0; i--) a.push_back(num1[i] - '0'); for (int i = num2.size() - 1; i >= 0; i--) b.push_back(num2[i] - '0'); auto product=a*b; int carry=0; for (int i=0;i<product.size();i++){ product[i]+=carry; carry=product[i]/10; product[i]%=10; } while (carry){ product.push_back(carry%10); carry/=10; } while (product.size()>1&&product.back()==0) product.pop_back(); string result; for (int i=product.size()-1;i>=0;i--) result+=to_string(product[i]); return result; } int main(){ string a,b; cin>>a>>b; string result=multiplyStrings(a,b); cout<<result<<endl; return 0; } ```echarts -
0
#include <bits/stdc++.h> using namespace std; // 大整数乘法函数 vector<int> mul(vector<int> &A, vector<int> &B) { // 结果数组,大小为 A 和 B 的长度之和 vector<int> C(A.size() + B.size(), 0); // 模拟乘法过程 for (int i = 0; i < A.size(); i++) { for (int j = 0; j < B.size(); j++) { // 对应位相乘并累加到结果数组的相应位置 C[i + j] += A[i] * B[j]; } } // 处理进位 int t = 0; for (int i = 0; i < C.size(); i++) { t += C[i]; C[i] = t % 10; t /= 10; } // 去除前导零 while (C.size() > 1 && C.back() == 0) { C.pop_back(); } return C; } int main() { string a, b; vector<int> A, B; cin >> a >> b; // 将输入的字符串转换为整数数组,低位在前 for (int i = a.length() - 1; i >= 0; i--) { A.push_back(a[i] - '0'); } for (int i = b.length() - 1; i >= 0; i--) { B.push_back(b[i] - '0'); } // 调用乘法函数 vector<int> ans = mul(A, B); // 输出结果 for (int i = ans.size() - 1; i >= 0; i--) { cout << ans[i]; } cout << endl; return 0; }
- 1
信息
- ID
- 5361
- 时间
- 1000ms
- 内存
- 125MiB
- 难度
- 3
- 标签
- 递交数
- 106
- 已通过
- 47
- 上传者