高精度（未完成）

mobaiawa · 2024-02-20 10:30:04 · 算法·理论

#include<bits/stdc++.h>
#define ll long long
#define lll vector<int>
#define sll node
using namespace std;
const ll N=1e6+10;
struct node{
    bool op;//1为负 
    lll dat;
};
lll _(ll x){
    lll c;
    if(x==0)c.push_back(0);
    else while(x){c.push_back(x%10);x/=10;}
    return c;
}
sll __(ll x){
    sll c;
    if(x<0){c.op=1;x=-x;}
    c.dat=_(x);
    return c;
}
bool operator==(const lll &a,const lll &b){
    if(a.size()==b.size()){
        bool flag=1;
        ll l=a.size();
        for(ll i=l-1;i>=0;i--){
            if(a[i]!=b[i]){
                flag=0;
                break;
            }
        }
        return flag;
    }
    return false;
}
bool operator!=(const lll &a,const lll &b){
    return !(a==b);
}
bool operator<(const lll &a,const lll &b){
    if(a.size()==b.size()){
        bool flag=0;
        ll l=a.size();
        for(ll i=l-1;i>=0;i--){
            if(a[i]<b[i]){
                flag=1;
                break;
            }
            else if(a[i]==b[i])continue;
            else break;
        }
        return flag;
    }
    return a.size()<b.size();
}
bool operator<(const node&a,const node&b){
    if(a.op==1&&b.op==0)return true;
    if(a.op==0&&b.op==1)return false;
    if(a.op==0)return a.dat<b.dat;
    if(a.op==1)return b.dat<a.dat;
    return a.dat.size()<b.dat.size();
}
bool operator>(const lll &a,const lll &b){
    return b<a;
}
bool operator>=(const lll &a,const lll &b){
    return a==b||b<a;
}
bool operator<=(const lll &a,const lll &b){
    return a==b||a<b;
}
bool operator>(const node&a,const node&b){
    return b<a;
}
bool operator==(const node&a,const node&b){
    return (a.op==b.op)&&a.dat==b.dat;
}
bool operator<=(const node&a,const node&b){
    return a<b||b==a;
}
bool operator>=(const node&a,const node&b){
    return b<a||b==a;
}
bool check(lll x,lll y,ll begin,ll len){
    lll a(x.begin()+begin,x.begin()+begin+len),b=y;
    while(a[a.size()-1]==0)a.resize(a.size()-1);
    return a>=b;
}
void get(node &a){
    a.dat.resize(0);
    char s[N];
    bool flag=0;
    scanf("%s",s);
    ll len=strlen(s);
    if(s[0]=='-'){
        a.op=1;
        flag=1;
    }
    else a.op=0;
    for(ll i=len-1;i>=flag;i--)a.dat.push_back(s[i]-'0');
}
void put(node a){
    if(a.op==1)putchar('-');
    for(ll i=a.dat.size()-1;i>=0;i--)putchar(a.dat[i]+'0');
//  putchar('\n');
}
void get(lll &a){
    a.resize(0);
    char s[N];
    scanf("%s",s);
    ll len=strlen(s);
    for(ll i=len-1;i>=0;i--)a.push_back(s[i]-'0');
}
void put(lll a){
    for(ll i=a.size()-1;i>=0;i--)putchar(a[i]+'0');
//  putchar('\n');
}
lll operator-(const lll &x,const lll &y){//a>=b
    lll a=x,b=y,c;
    ll l=max(a.size(),b.size());
    c.resize(l);
    a.resize(l);
    b.resize(l);
    for(ll i=0;i<l;i++){
        c[i]+=a[i]-b[i];
        if(c[i]<0){
            c[i+1]-=1;
            c[i]+=10;
        }
    }
    ll cnt=0;
    while(c[c.size()-1-cnt]==0)cnt++;
    c.resize(c.size()-cnt);
    return c;
}
lll operator+(const lll &x,const lll &y){
    lll a=x,b=y,c;
    ll l=max(a.size(),b.size());
    c.resize(l);
    a.resize(l);
    b.resize(l);
    ll m=0;
    for(ll i=0;i<l;i++){
        c[i]=(a[i]+b[i]+m)%10;
        m=(a[i]+b[i]+m)/10;
    }
    if(m>0)c.push_back(m);
    return c;
}
lll operator*(const lll &x,const lll &y){
    lll a=x,b=y,c;
    if(a[0]==0&&a.size()==1||b[0]==0&&b.size()==1)c.push_back(0);
    else{
        if(a<b)swap(a,b);
        c.resize(a.size()+b.size()-1);
        for(ll i=0;i<a.size();i++){
            for(ll j=0;j<b.size();j++)c[i+j]+=a[i]*b[j];
        }
        for(ll i=0;i<c.size()-1;i++){
            c[i+1]+=c[i]/10;
            c[i]%=10;
        }
        while(c[c.size()-1]/10){
            c.push_back(c[c.size()-1]/10);
            c[c.size()-2]%=10;
        }
    }
    return c;
}
lll operator*(const lll &x,const ll &y){
    lll a=x,c;
    ll b=y;
    if(a[0]==0&&a.size()==1||b==0)c.push_back(0);
    else{
        ll cnt=0,d=b;
        while(d){
            cnt++;
            d/=10;
        }
        c.resize(a.size()+cnt-1);
        for(ll i=0;i<a.size();i++)c[i]=a[i]*b;
        for(ll i=0;i<c.size()-1;i++){
            c[i+1]+=c[i]/10;
            c[i]%=10;
        }
        while(c[c.size()-1]/10){
            c.push_back(c[c.size()-1]/10);
            c[c.size()-2]%=10;
        }
    }
    return c;
}
lll operator/(const lll &x,const lll &y){
    lll a=x,b=y,c;
    if(y.size()==1&&y[0]==0)return c;
    if(x.size()==1&&x[0]==0)c.push_back(0);
    else{
        c.resize(max(a.size(),b.size()));
        for(ll i=a.size()-b.size();i>=0;i--){
            while(check(a,b,i,a.size()-i)){
                for(ll j=0;j<b.size();j++){
                    a[i+j]-=b[j];
                    if(a[i+j]<0){
                        a[i+j+1]--;
                        a[i+j]+=10;
                    }
                }
                c[i]++;
            }
        }
    }
    ll cnt=0;
    while(c[c.size()-1-cnt]==0&&c.size()-cnt>1)cnt++;
    c.resize(c.size()-cnt);
    return c;
}
lll operator/(const lll &x,const ll &y){
    lll a=x,c;
    if(y==0)return c;
    if(y==1)return x;
    c.resize(a.size());
    ll r=0;
    for(ll i=a.size()-1;i>=0;i--){
        r=r*10+a[i];
        c.push_back(r/y);
        r%=y;
    }
    reverse(c.begin(),c.end());
    ll cnt=0;
    while(c.size()-cnt>1&&c[c.size()-cnt-1]==0)cnt++;
    c.resize(c.size()-cnt);
    return c;
}
ll operator%(const lll &x,const ll &y){
    lll a=x;
    ll r=0;
    for(ll i=a.size()-1;i>=0;i--){
        r=r*10+a[i];
        r%=y;
    }
    return r;
}
lll operator%(const lll &x,const lll &y){
    lll a=x,b=y,c;
    for(ll i=a.size()-b.size();i>=0;i--){
        while(check(a,b,i,a.size()-i)){
            for(ll j=0;j<b.size();j++){
                a[i+j]-=b[j];
                if(a[i+j]<0){
                    a[i+j+1]--;
                    a[i+j]+=10;
                }
            }
        }
    }
    ll cnt=0;
    while(a[a.size()-cnt-1]==0&&a.size()-cnt>1)cnt++;
    a.resize(a.size()-cnt);
    return a;
}
node operator-(const node &x,const node &y){
    node a=x,b=y,c;
    if(a==b){
        c.op=0;
        c.dat.push_back(0);
    }
    else if(a.op=0&&b.op==1){
        c.op=0;
        c.dat=a.dat+b.dat;
    }
    else if(a.op==1&&b.op==0){
        c.op=1;
        c.dat=a.dat+b.dat;
    }
    else if(a.op==1&&b.op==1){
        if(a<b){
            c.op=1;
            c.dat=a.dat-b.dat;
        }
        else{
            c.op=0;
            c.dat=b.dat-a.dat;
        }
    }
    else if(a.op==0&&b.op==0){
        if(a<b){
            c.op=1;
            c.dat=b.dat-a.dat;
        }
        else{
            c.op=0;
            c.dat=a.dat-b.dat;
        }
    }
    return c;
}
node operator+(const node &x,const node &y){
    node a=x,b=y,c;
    if(a<b)swap(a,b);
    if(a.op==b.op){
        c.op=a.op;
        c.dat=a.dat+b.dat;
    }
    else{
        if(a.dat<b.dat){
            c.op=1;
            c.dat=b.dat-a.dat;
        }
        else{
            c.op=0;
            c.dat=a.dat-b.dat;
        }
    }
    return c;
}
node operator*(const node &x,const node &y){
    node a=x,b=y,c;
    c.op=a.op^b.op;
    c.dat=a.dat*b.dat;
    return c;
}
node operator/(const node &x,const node &y){
    node a=x,b=y,c;
    c.op=a.op^b.op;
    c.dat=a.dat/b.dat;
    return c;
}
int main(){
    return 0;
}