高精模板_牛客博客

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=10002,M=1e9;
struct NUM{
    int t;
    ll a[N/9];
    friend void print(NUM x){
        if (!x.t){puts("0");return;}
        printf("%lld",x.a[--x.t]);
        int t[9];
        for (int i=x.t-1;i>=0;i--){
            memset(t,0,sizeof(t));
            for (int j=0;j<9;j++) t[j]=x.a[i]%10,x.a[i]/=10;
            for (int j=8;j>=0;j--) putchar(t[j]|48);
        }
        puts("");
    }
    friend bool operator>(NUM x,NUM y){
        if (x.t!=y.t) return x.t>y.t;
        for (int i=x.t-1;i>=0;i--)
            if (x.a[i]!=y.a[i]) return x.a[i]>y.a[i];
        return 0;
    }
    friend NUM operator+(NUM x,NUM y){
        int i;
        for (i=0;i<x.t || i<y.t || x.a[i];i++){
            if (i+1>=x.t) x.a[i+1]=0;
            if (i<y.t) x.a[i]+=y.a[i];
            if (x.a[i]>=M) x.a[i+1]++,x.a[i]-=M;
        }
        x.t=i;
        return x;
    }
    friend NUM operator-(NUM x,NUM y){
        if (y>x) swap(x,y);
        for (int i=0;i<y.t;i++){
            x.a[i]-=y.a[i];
            if (x.a[i]<0) x.a[i]+=M,x.a[i+1]--;
        }
        while (x.t && !x.a[x.t-1]) x.t--;
        return x;
    }
    friend NUM operator*(NUM x,NUM y){
        NUM z;z.t=x.t+y.t;
        memset(z.a,0,z.t<<3);
        for (int i=0;i<x.t;i++)
            for (int j=0;j<y.t;j++){
                z.a[i+j]+=x.a[i]*y.a[j];
                z.a[i+j+1]+=z.a[i+j]/M;
                z.a[i+j]%=M;
            }
        if (z.t && !z.a[z.t-1]) z.t--;
        return z;
    }
    friend NUM operator*(NUM x,int y){
        int i;
        for (i=0;i<x.t;i++) x.a[i]*=y;
        for (i=0;i<x.t || x.a[i];i++){
            if (i+1>=x.t) x.a[i+1]=0;
            x.a[i+1]+=x.a[i]/M,x.a[i]%=M;
        }
        x.t=i;
        return x;
    }
    friend NUM operator/(NUM x,int y){
        ll k=0;
        for (int i=x.t-1;i>=0;i--){
            k=k*M+x.a[i];
            x.a[i]=k/y;
            k%=y;
        }
        while (x.t && !x.a[x.t-1]) x.t--;
        return x;
    }
    friend NUM div(NUM x,NUM y,bool fl){
        NUM z;z.t=x.t-y.t+1;
        if (z.t<=0){
            z.t=0;
            return fl?z:x;
        }
        memset(z.a,0,z.t<<3);
        for (int i=z.t-1;i>=0;i--){
            for (int j=1<<29;j;j>>=1){
                NUM tmp=y*j;bool fl=tmp.t+i<=x.t;
                if (!fl) continue;
                if (tmp.t+i==x.t){
                    for (int k=tmp.t-1;k>=0;k--)
                        if (x.a[k+i]!=tmp.a[k]){
                            fl=tmp.a[k]<x.a[k+i];
                            break;
                        }
                    if (!fl) continue;
                }
                z.a[i]|=j;
                for (int k=0;k<tmp.t;k++){
                    x.a[k+i]-=tmp.a[k];
                    if (x.a[k+i]<0) x.a[k+i+1]--,x.a[k+i]+=M;
                }
                while (x.t && !x.a[x.t-1]) x.t--;
            }
        }
        while (z.t && !z.a[z.t-1]) z.t--;
        return fl?z:x;
    }
    friend NUM operator/(NUM x,NUM y){return div(x,y,1);}
    friend NUM operator%(NUM x,NUM y){return div(x,y,0);}
    friend NUM gcd(NUM x,NUM y){
        int cnt=0;NUM T;
        while (1){
            if (!x.t || !y.t){
                NUM p,z;
                p.a[0]=2;
                p.t=z.t=z.a[0]=1;
                for (;cnt;cnt>>=1,p=p*p)
                    if (cnt&1) z=z*p;
                if (x.t) return z*x;
                else return z*y;
            }
            bool f1=0,f2=0;
            if (!(x.a[0]&1)) x=x/2,f1=1;
            if (!(y.a[0]&1)) y=y/2,f2=1;
            if (f1 && f2) cnt++;
            if (x>y) x=x-y;
            else T=x,x=y-x,y=T;
        }
    }
}E;
NUM toNUM(char s[]){
    ll f[10];
    f[0]=1;
    for (int i=1;i<10;i++) f[i]=f[i-1]*10;
    NUM A;
    A.t=strlen(s);
    memset(A.a,0,(A.t-1)/9+1<<3);
    for (int i=A.t-1;i>=0;i--) A.a[(A.t-1-i)/9]+=f[(A.t-1-i)%9]*(s[i]^48);
    A.t=(A.t-1)/9+1;
    return A;
}
int main(){
	E.t=E.a[0]=1;
}