时间戳

首页 > 技术文章 > 高精度合集(朴素)

高精度合集(朴素)

GK0328 2020-08-17 14:40 原文

https://www.luogu.com.cn/problem/P1932

高精度合集(朴素)

高精度合集(NTT优化乘法)

高精度合集(vector)

高精度合集(vector,带低精)

待补:压位高精,多项式除法优化除法、取模

Luogu1932 A+B A-B A*B A/B A%B Problem

高精度合集(朴素)

朴素(无符号)

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define N 20005
#define ll long long
#define a hz.w
#define b kz.w
#define c kzkz.w
#define d kzzf.w
#define zero(x) (x.w[0]==1 && x.w[1]==0)
using namespace std;
char orz[N];
struct BigNumber
{
    int w[N];
    void set0()
    {
        w[0]=1,w[1]=0;
    }
    void set1()
    {
        w[0]=1,w[1]=1;
    }
    void read()
    {
        scanf("%s",orz);
        w[0]=strlen(orz);
        for (int i=0;i<w[0];i++)
            w[w[0]-i]=orz[i]-'0';
    }
}s,t;
void write(BigNumber kz)
{
    for (int i=b[0];i>=1;i--)
        putchar(b[i]+'0');
    putchar('\n');
}
bool operator < (BigNumber hz,BigNumber kz)
{
    if (a[0]!=b[0])
        return a[0]<b[0];
    for (int i=a[0];i>=1;i--)
        if (a[i]!=b[i])
            return a[i]<b[i];
    return false;
}
bool operator <= (BigNumber hz,BigNumber kz)
{
    if (a[0]!=b[0])
        return a[0]<b[0];
    for (int i=a[0];i>=1;i--)
        if (a[i]!=b[i])
            return a[i]<b[i];
    return true;
}
bool operator > (BigNumber hz,BigNumber kz)
{
    if (a[0]!=b[0])
        return a[0]>b[0];
    for (int i=a[0];i>=1;i--)
        if (a[i]!=b[i])
            return a[i]>b[i];
    return false;
}
bool operator >= (BigNumber hz,BigNumber kz)
{
    if (a[0]!=b[0])
        return a[0]>b[0];
    for (int i=a[0];i>=1;i--)
        if (a[i]!=b[i])
            return a[i]>b[i];
    return true;
}
bool operator == (BigNumber hz,BigNumber kz)
{
    if (a[0]!=b[0])
        return false;
    for (int i=a[0];i>=1;i--)
        if (a[i]!=b[i])
            return false;
    return true;
}
bool operator != (BigNumber hz,BigNumber kz)
{
    if (a[0]!=b[0])
        return true;
    for (int i=a[0];i>=1;i--)
        if (a[i]!=b[i])
            return true;
    return false;
}
BigNumber operator + (BigNumber hz,BigNumber kz)
{
    int ws=max(a[0],b[0]);
    int jw=0;
    for (int i=1;i<=ws;i++)
    {
        if (a[0]<i)
            a[i]=0;
        if (b[0]<i)
            b[i]=0;
        b[i]=b[i]+a[i]+jw;
        jw=b[i]/10;
        b[i]%=10;
    }
    while (jw)
    {
        ws++;
        b[ws]=jw%10;
        jw/=10;
    }
    b[0]=ws;
    return kz;
}
BigNumber operator - (BigNumber hz,BigNumber kz)
{
    int ws=max(a[0],b[0]);
    for (int i=1;i<=ws;i++)
    {
        if (i>b[0])
            b[i]=a[i]; else
            b[i]=a[i]-b[i];
        if (b[i]<0)
        {
            b[i]+=10;
            a[i+1]--;
        }
    }
    while (!b[ws] && ws>1)
        ws--;
    b[0]=ws;
    return kz;
}
BigNumber operator * (BigNumber hz,BigNumber kz)
{
    int la=a[0],lb=b[0];
    BigNumber kzkz;
    for (int i=0;i<=la+lb;i++)
        c[i]=0;
    for (int i=1;i<=la;i++)
        for (int j=1;j<=lb;j++)
        {
            c[i+j-1]+=a[i]*b[j];
            c[i+j]+=c[i+j-1]/10;
            c[i+j-1]%=10;
        }
    c[0]=la+lb;
    while (!c[c[0]] && c[0]>1)
        c[0]--;
    return kzkz;
}
BigNumber operator / (BigNumber hz,BigNumber kz)
{
    BigNumber kzkz,kzzf;
    for (int i=0;i<=a[0];i++)
        c[i]=d[i]=0;
    d[0]=1;
    for (int i=a[0];i>=1;i--)
    {
        if (!(d[0]==1 && d[1]==0))
        {
            for (int i=d[0];i>=1;i--)
                d[i+1]=d[i];
            d[1]=a[i];
            d[0]++;
        } else
            d[1]=a[i];
        while (kzzf>=kz)
        {
            kzzf=kzzf-kz;
            c[i]++;
        }
    }
    c[0]=a[0];
    while (!c[c[0]] && c[0]>1)
        c[0]--;
    return kzkz;
}
BigNumber operator % (BigNumber hz,BigNumber kz)
{
    BigNumber kzzf;
    for (int i=0;i<=a[0];i++)
        d[i]=0;
    d[0]=1;
    for (int i=a[0];i>=1;i--)
    {
        if (!(d[0]==1 && d[1]==0))
        {
            for (int i=d[0];i>=1;i--)
                d[i+1]=d[i];
            d[1]=a[i];
            d[0]++;
        } else
            d[1]=a[i];
        while (kzzf>=kz)
            kzzf=kzzf-kz;
    }
    return kzzf;
}
void operator += (BigNumber &kz,BigNumber hz)
{
    kz=kz+hz;
}
void operator -= (BigNumber &kz,BigNumber hz)
{
    kz=kz-hz;
}
void operator *= (BigNumber &kz,BigNumber hz)
{
    kz=kz*hz;
}
void operator /= (BigNumber &kz,BigNumber hz)
{
    kz=kz/hz;
}
void operator %= (BigNumber &kz,BigNumber hz)
{
    kz=kz%hz;
}
BigNumber Number_Turn_BigNumber(ll x)
{
    BigNumber kz;
    if (x==0)
    {
        kz.set0();
        return kz;
    }
    b[0]=0;
    while (x)
    {
        b[++b[0]]=x%10;
        x/=10;
    }
    return kz;
}
ll BigNumber_Turn_Number(BigNumber kz)
{
    ll y=0;
    for (int i=b[0];i>=1;i--)
        y=y*10+b[i];
    return y;
}
int main()
{
    s.read(),t.read();
    write(s+t);
    if (s<t)
        putchar('-'),write(t-s); else
        write(s-t);
    write(s*t);
    write(s/t);
    write(s%t);
    return 0;
}

朴素(带符号)

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define N 20005
#define ll long long
#define a hz.w
#define b kz.w
#define c kzkz.w
#define d kzzf.w
#define hp hz.p
#define kp kz.p
#define cp kzkz.p
#define dp kzzf.p
#define zero(x) (x.w[0]==1 && x.w[1]==0)
using namespace std;
char orz[N];
struct BigNumber
{
    int w[N];
    bool p=true;
    void set0()
    {
        w[0]=1,w[1]=0,p=true;
    }
    void set1()
    {
        w[0]=1,w[1]=1,p=true;
    }
    void read()
    {
        scanf("%s",orz);
        w[0]=strlen(orz);
        if (orz[0]=='-')
        {
            p=false;
            w[0]--;
            for (int i=1;i<=w[0];i++)
                w[w[0]-i+1]=orz[i]-'0';
        } else
        {
            p=true;
            for (int i=0;i<w[0];i++)
                w[w[0]-i]=orz[i]-'0';
        }
    }
}s,t;
void write(BigNumber kz)
{
    if (!kz.p)
        putchar('-');
    for (int i=b[0];i>=1;i--)
        putchar(b[i]+'0');
    putchar('\n');
}
bool operator > (BigNumber hz,BigNumber kz);
bool operator < (BigNumber hz,BigNumber kz)
{
    if (hp!=kp)
        return kp;
    if (!hp)
    {
        hp=kp=true;
        return hz>kz;
    }
    if (a[0]!=b[0])
        return a[0]<b[0];
    for (int i=a[0];i>=1;i--)
        if (a[i]!=b[i])
            return a[i]<b[i];
    return false;
}
bool operator >= (BigNumber hz,BigNumber kz);
bool operator <= (BigNumber hz,BigNumber kz)
{
    if (hp!=kp)
        return kp;
    if (!hp)
    {
        hp=kp=true;
        return hz>=kz;
    }
    if (a[0]!=b[0])
        return a[0]<b[0];
    for (int i=a[0];i>=1;i--)
        if (a[i]!=b[i])
            return a[i]<b[i];
    return true;
}
bool operator > (BigNumber hz,BigNumber kz)
{
    if (hp!=kp)
        return hp;
    if (!hp)
    {
        hp=kp=true;
        return hz<kz;
    }
    if (a[0]!=b[0])
        return a[0]>b[0];
    for (int i=a[0];i>=1;i--)
        if (a[i]!=b[i])
            return a[i]>b[i];
    return false;
}
bool operator >= (BigNumber hz,BigNumber kz)
{
    if (hp!=kp)
        return hp;
    if (!hp)
    {
        hp=kp=true;
        return hz<=kz;
    }
    if (a[0]!=b[0])
        return a[0]>b[0];
    for (int i=a[0];i>=1;i--)
        if (a[i]!=b[i])
            return a[i]>b[i];
    return true;
}
bool operator == (BigNumber hz,BigNumber kz)
{
    if (hp!=kp)
        return false;
    if (a[0]!=b[0])
        return false;
    for (int i=a[0];i>=1;i--)
        if (a[i]!=b[i])
            return false;
    return true;
}
bool operator != (BigNumber hz,BigNumber kz)
{
    if (hp!=kp)
        return true;
    if (a[0]!=b[0])
        return true;
    for (int i=a[0];i>=1;i--)
        if (a[i]!=b[i])
            return true;
    return false;
}
BigNumber operator - (BigNumber hz,BigNumber kz);
BigNumber operator + (BigNumber hz,BigNumber kz)
{
    if (zero(hz))
        return kz;
    if (zero(kz))
        return hz;
    if (hp!=kp)
    {
        if (!kp)
        {
            kp=!kp;
            return hz-kz;
        } else
        {
            hp=!hp;
            return kz-hz;
        }
    }
    int ws=max(a[0],b[0]);
    int jw=0;
    for (int i=1;i<=ws;i++)
    {
        if (a[0]<i)
            a[i]=0;
        if (b[0]<i)
            b[i]=0;
        b[i]=b[i]+a[i]+jw;
        jw=b[i]/10;
        b[i]%=10;
    }
    while (jw)
    {
        ws++;
        b[ws]=jw%10;
        jw/=10;
    }
    b[0]=ws;
    if (zero(kz))
        kp=true;
    return kz;
}
BigNumber operator - (BigNumber hz,BigNumber kz)
{
    if (zero(kz))
        return hz;
    if (zero(hz))
    {
        kp=!kp;
        return kz;
    }
    if (!hp && kp)
    {
        kp=!kp;
        return hz+kz;
    }
    if (hp && !kp)
    {
        kp=!kp;
        return hz+kz;
    }
    if (!hp && !kp)
    {
        hp=!hp,kp=!kp;
        swap(hz,kz);
    }
    bool gk=true;
    if (hz<kz)
    {
        gk=false;
        swap(hz,kz);
    }
    int ws=max(a[0],b[0]);
    for (int i=1;i<=ws;i++)
    {
        if (i>b[0])
            b[i]=a[i]; else
            b[i]=a[i]-b[i];
        if (b[i]<0)
        {
            b[i]+=10;
            a[i+1]--;
        }
    }
    while (!b[ws] && ws>1)
        ws--;
    b[0]=ws;
    if (!gk)
        kp=!kp;
    if (zero(kz))
        kp=true;
    return kz;
}
BigNumber operator * (BigNumber hz,BigNumber kz)
{
    int la=a[0],lb=b[0];
    BigNumber kzkz;
    cp=!(hp^kp);
    for (int i=0;i<=la+lb;i++)
        c[i]=0;
    for (int i=1;i<=la;i++)
        for (int j=1;j<=lb;j++)
        {
            c[i+j-1]+=a[i]*b[j];
            c[i+j]+=c[i+j-1]/10;
            c[i+j-1]%=10;
        }
    c[0]=la+lb;
    while (!c[c[0]] && c[0]>1)
        c[0]--;
    if (zero(kzkz))
        cp=true;
    return kzkz;
}
BigNumber operator / (BigNumber hz,BigNumber kz)
{
    BigNumber kzkz,kzzf;
    if (zero(hz))
    {
        kzkz.set0();
        return kzkz;
    }
    if (hp!=kp)
        cp=false; else
        cp=true;
    hp=kp=true;
    for (int i=0;i<=a[0];i++)
        c[i]=d[i]=0;
    d[0]=1;
    for (int i=a[0];i>=1;i--)
    {
        if (!(d[0]==1 && d[1]==0))
        {
            for (int i=d[0];i>=1;i--)
                d[i+1]=d[i];
            d[1]=a[i];
            d[0]++;
        } else
            d[1]=a[i];
        while (kzzf>=kz)
        {
            kzzf=kzzf-kz;
            c[i]++;
        }
    }
    c[0]=a[0];
    while (!c[c[0]] && c[0]>1)
        c[0]--;
    if (zero(kzkz))
        cp=true;
    return kzkz;
}
BigNumber operator % (BigNumber hz,BigNumber kz)
{
    BigNumber kzzf;
    if (zero(hz))
    {
        kzzf.set0();
        return kzzf;
    }
    bool gk;
    gk=hp;
    hp=kp=true;
    for (int i=0;i<=a[0];i++)
        d[i]=0;
    d[0]=1;
    for (int i=a[0];i>=1;i--)
    {
        if (!(d[0]==1 && d[1]==0))
        {
            for (int i=d[0];i>=1;i--)
                d[i+1]=d[i];
            d[1]=a[i];
            d[0]++;
        } else
            d[1]=a[i];
        while (kzzf>=kz)
            kzzf=kzzf-kz;
    }
    dp=gk;
    if (zero(kzzf))
        dp=true;
    return kzzf;
}
void operator += (BigNumber &kz,BigNumber hz)
{
    kz=kz+hz;
}
void operator -= (BigNumber &kz,BigNumber hz)
{
    kz=kz-hz;
}
void operator *= (BigNumber &kz,BigNumber hz)
{
    kz=kz*hz;
}
void operator /= (BigNumber &kz,BigNumber hz)
{
    kz=kz/hz;
}
void operator %= (BigNumber &kz,BigNumber hz)
{
    kz=kz%hz;
}
BigNumber Number_Turn_BigNumber(ll x)
{
    BigNumber kz;
    if (x==0)
    {
        kz.set0();
        kp=true;
        return kz;
    }
    if (x<0)
    {
        kp=false;
        x=-x;
    } else
        kp=true;
    b[0]=0;
    while (x)
    {
        b[++b[0]]=x%10;
        x/=10;
    }
    return kz;
}
ll BigNumber_Turn_Number(BigNumber kz)
{
    ll y=0;
    for (int i=b[0];i>=1;i--)
        y=y*10+b[i];
    if (!kp)
        y=-y;
    return y;
}
int main()
{
    s.read(),t.read();
    write(s+t);
    write(s-t);
    write(s*t);
    write(s/t);
    write(s%t);
    return 0;
}

推荐阅读