3 条题解

  • 0
    @ 2025-10-28 18:39:42

    本题可以用快速傅里叶变换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
      @ 2025-3-1 21:47:58
      #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

        #include<bits/stdc++.h>

        using namespace std;、

        int main(){ int a,b; cin>>a>>b;

        cout<<a*b;
        

        }

        • 1

        信息

        ID
        5361
        时间
        1000ms
        内存
        125MiB
        难度
        3
        标签
        递交数
        106
        已通过
        47
        上传者