请问这个代码为什么会运行错误
  • 板块学术版
  • 楼主YangJinxi_7_22
  • 当前回复3
  • 已保存回复3
  • 发布时间2023/11/15 16:24
  • 上次更新2023/11/15 18:57:57
查看原帖
请问这个代码为什么会运行错误
505959
YangJinxi_7_22楼主2023/11/15 16:24

我想用一个BigInteger类来实现高精度,其中重载了*进行高精度乘法但不知道为什么,运行代码的时候出现了Process finished with exit code 139 (interrupted by signal 11: SIGSEGV)的错误,哪位大佬可以帮我看一下,谢谢。

#include <iostream>
#include <cstring>
#include <vector>
#include <complex>
using namespace std;
const double PI = acos(-1.0);
static const int M = 3e6+5;

struct BigInteger{
    string s;
    BigInteger(string _s="", bool pos = 1): s(_s){}
    bool operator == (const BigInteger& bgi ){
        if( s.size() != bgi.s.size() ) return 0;
        else{
            for(int i = 0; i < s.size( ); i++){
                if( s[i] != bgi.s[i] ) return 0;
            }
        }
        return 1;
    }
    bool operator <( const BigInteger& bgi ){
        if( s.size( ) < bgi.s.size() ) return 1;
        else if( s.size() > bgi.s.size() ) return 0;
        else{
            int n = s.size();
            for(int i = 0; i < n; i--){
                if( s[i] > bgi.s[i] ) return 0;
                else if( s[i] < bgi.s[i] ) return 1;
            }
        }
        return 0;
    }
    bool operator <= ( const BigInteger& bgi ){
        if( (*this) < bgi || (*this) == bgi ) return 1;
        else return 0;
    }
    bool operator > (const BigInteger& bgi ){
        if( s.size( ) < bgi.s.size() ) return 0;
        else if( s.size() > bgi.s.size() ) return 1;
        else{
            int n = s.size();
            for(int i = 0; i < n; i--){
                if( s[i] < bgi.s[i] ) return 0;
                else if( s[i] > bgi.s[i] ) return 1;
            }
        }
        return 0;
    }
    bool operator >= (const BigInteger& bgi ){
        if( (*this) > bgi || (*this) == bgi ) return 1;
        else return 0;
    }
};

vector<int> toIntArray( BigInteger b ){
    int n = b.s.size();
    vector<int> res;
    res.resize(n+5);
    for(int i = 0; i < n; i++){
        res[n-i-1] = b.s[i]-'0';
    }
    return res;
}

BigInteger toBigInteger( const vector<int>& v ){
    int n = v.size();
    int st = n-1;
    while( st >= 0 && !v[st] ) --st;
    if( st == -1 ) return BigInteger("0");
    string s;
    for(int i = st; i >= 0; i--){
        s += ('0'+v[i]);
    }
    return BigInteger(s);
}

BigInteger operator + (BigInteger b1, BigInteger b2){
    if( b1 < b2 ) swap(b1,b2);
    int n = b1.s.size(), m = b2.s.size();
    vector<int> a,b;
    a = toIntArray(b1);
    b = toIntArray(b2);
    for(int i = 0; i < m; i++){
        a[i] += b[i];
        if( a[i] >= 10 ) a[i+1] += a[i]/10;
        a[i] %= 10;
    }
    return toBigInteger(a);
}

void init( vector<int> rev , int k){
    int len =  (1<<k);
    rev.resize(len);
    for(int i = 0; i < len; i++){
        rev[i] = ((rev[i>>1]>>1)|(i&1)<<(k-1));
    }
}

//flag=1:快速傅里叶变换,flag=-1:逆快速傅里叶变换
//a表示变换后的结果,n表示多项式的长度,rev表示多项式分解后各项的顺序
void FFT(vector<complex<double> > &a, int n, int flag, vector<int> rev){
    a.resize(n);
    for(int i = 0; i < n; i++ ){
        if( i < rev[i] ){
            swap(a[i],a[rev[i]]);
        }
    }
    for(int h = 1; h < n; h >>= 1){
        complex<double> wn = exp(complex<double>(0,flag*PI/h));
        for(int j = 0; j < n; j += h*2){
            complex<double> w(1,0);
            for(int k = j; k < j+h; k++){
                complex<double> x = a[k];
                complex<double> y = w*a[k+h];
                a[k] = x+y;
                a[k+h] = x-y;
                w *= wn;
            }
        }
    }
    if( flag == -1 ){
        for(int i = 0; i < n; i++){
            a[i] /= n;
        }
    }
}

BigInteger operator *( const BigInteger& A, const BigInteger& B){
    string s1 = A.s, s2 = B.s;
    int n = s1.size(), m = s2.size();
    vector<complex<double> > a, b;
    a.resize(n);
    b.resize(m);
    for(int i = 0; i < n; i++){
        a[n-i-1] = s1[i]-'0';
    }
    for(int i = 0; i < m; i++){
        b[m-i-1] = s2[i]-'0';
    }
    int k = 1, s = 2;
    while( (1<<k) < n+m-1 ){
        ++k;
        s <<= 1;
    }
    vector<int> rev;
    init(rev,k);
    FFT(a,s,1,rev);
    FFT(b,s,1,rev);
    for(int i = 0; i < s; i++){
        a[i] *= b[i];
    }
    FFT(a,s,-1,rev);
    vector<int> ans;
    ans.resize(s);
    for(int i = 0; i < s; i++){
        ans[i] = (int)(a[i].real()+0.5);
        ans[i+1] += ans[i]/10;
        ans[i] %= 10;
    }
    return toBigInteger(ans);
}

int main() {
    string s1, s2;
    cin >> s1 >> s2;
    BigInteger a(s1), b(s2), c;
    c = a*b;
    cout << c.s <<endl;
    return 0;    
}
2023/11/15 16:24
加载中...