70分求助
查看原帖
70分求助
371848
吴思诚楼主2025/8/4 22:38
#include<cstring>
#include<iostream>
#include<iomanip>
#include<algorithm>
#define mem cerr<<abs(&_v-&_u)/1024.0/1024<<"MB\n"
#define A *this
using ull=unsigned long long;
using ll=long long;
using namespace std;
const int N=2010;//压位后位数
const int M=10010;//输入大数长度
const int W=10;//压位数
const ull k=1e10;//进制模数
bool _u;
char output[20];//用于printf输出前导0
struct bigInt{
    ull a[N];
    //maxn=18446744073709551615
    //因此压18位,如果压19位,(10^19-1)*2>maxn,不可
    int len;//压位后实际长度
    int sign;//正负号
    template <typename T>
    bigInt(T x):len(1),sign(1){
        memset(a,0,sizeof(ull)*N);
        a[1]=x;
    }
    bigInt():len(1),sign(1){
        memset(a,0,sizeof(ull)*N);
    }
    void read(){
        char s[M];
        cin>>s;
        int n=strlen(s),r=(n+W-1)/W,c=W*r-n;
        len=r;
        ull x=0;
        for(int i=0;s[i];++i){
            ++c;
            x=x*10+s[i]-48;
            if(c==W){
                c=0;
                a[r--]=x;
                x=0;
            }
        }
        if(x)a[r--]=x;
    }
    void print(){
        if(sign==-1&&(len!=1||a[1]!=0))cout<<'-';
        cout<<a[len];
        for(int i=len-1;i;--i)
            cout<<setw(W)<<setfill('0')<<a[i];
        cout<<'\n';
    }
    bigInt& operator=(const bigInt&B){
        for(int i=1;i<=B.len;++i)a[i]=B.a[i];
        len=B.len;
        sign=B.sign;
        return A;
    }
    bigInt& operator=(int B){
        if(B<0)sign=-1,B=-B;
        len=1;
        a[1]=B;
        return A;
    }
    bigInt operator+(const bigInt&B)const{
        bigInt C;
        int m=max(len,B.len),t=0;
        C.len=m;
        for(int i=1;i<=m;++i){
            C.a[i]=t;
            if(i<=len)C.a[i]+=a[i];
            if(i<=B.len)C.a[i]+=B.a[i];
            t=C.a[i]/k;
            C.a[i]%=k;
        }
        if(t)C.a[++C.len]=t;
        return C;
    }
    void operator+=(const bigInt&B){
        A=A+B;
    }
    bool operator<(const bigInt&B)const{
        if(len!=B.len)return len<B.len;
        for(int i=len;i;--i)
            if(a[i]<B.a[i])return 1;
            else if(a[i]>B.a[i])return 0;
        return 0;
    }
    bool operator>(const bigInt&B)const{
        return !(A<B);
    }
    bool operator==(const bigInt&B)const{
        if(len!=B.len)return 0;
        for(int i=len;i;--i)
            if(a[i]!=B.a[i])return 0;
        return 1;
    }
    bool operator!=(const bigInt&B)const{
        return !(A==B);
    }
    bool operator<=(const bigInt&B)const{
        return A<B||A==B;
    }
    bool operator>=(const bigInt&B)const{
        return A>B||A==B;
    }
    bigInt operator-(bigInt B){
        bigInt C=max(A,B);
        if(C==B)C.sign=-1;
        B=min(A,B);
        for(int i=1;i<=B.len;++i)
            if(C.a[i]<B.a[i])--C.a[i+1],C.a[i]=C.a[i]+k-B.a[i];
            else C.a[i]-=B.a[i];
        while(C.len!=1&&!C.a[C.len])--C.len;
        return C;
    }
    void operator-=(bigInt&B){
        A=A-B;
    }
    bigInt operator*(bigInt&B){
        bigInt C;
        C.len=len+B.len-1;
        for(int i=1;i<=len;++i){
            ll c;
            for(int j=1;j<=B.len;++j){
                c=(long double)a[i]*B.a[j]/k;
                ll tmp=a[i]*B.a[j]-c*k;
                if(tmp<0)tmp+=k;
                C.a[i+j-1]+=tmp;
                C.a[i+j]+=c;
                C.a[i+j]+=C.a[i+j-1]/k;
                C.a[i+j-1]%=k;
            }}
        for(int i=0;i<C.len;++i)
            C.a[i+1]+=C.a[i]/k,C.a[i]%=k;
        if(C.a[C.len+1]>0)++C.len;
        C.sign=sign==B.sign?1:-1;
        return C;
    }
    void operator*=(bigInt&B){
        A=A*B;
    }
    template <typename T>
    bigInt operator/(T x){
        bigInt C;
        C.len=0;
        ull r=0;
        for(int i=len;i;--i){
            r=r*k+a[len];
            C.a[++C.len]=r/x;
            r%=x;
        }
        reverse(C.a+1,C.a+1+C.len);
        C.sign=(sign==x/abs(x))?1:-1;
        while(C.len!=1&&!C.a[len])--C.len;
        return C;
    }
    bigInt operator/(bigInt&B){
        bigInt l=0,r=A,tmp(1),mid;
        while(l<r){
            mid=(l+r+tmp)/2;
            if(mid*B<=A)l=mid;
            else r=mid-tmp;
        }
        return r;
    }
    void operator/=(bigInt&B){
        A=A/B;
    }
    bigInt operator%(bigInt&B){
        return A-A/B*B;
    }
    void operator%=(bigInt&B){
        A=A%B;
    }
};
bool _v;
int main(){
    #ifdef LOCAL
    freopen("1.txt","r",stdin);
    #endif
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    sprintf(output,"%%0%dllu",W);
    bigInt a,b,t;
    a.read(),b.read();
    (a+b).print();
    (a-b).print();
    (a*b).print();
    (a/b).print();
    (a%b).print();
    return 0;
}
2025/8/4 22:38
加载中...