背景

我们痛恨高精度。

介绍

不想写高精度怎么办？提前写好模板，要用时直接复制粘贴就好啦！以下是一个高精度类，实现了除除法、取模和位运算外的所有整形运算。（先咕着这些，以后会添加的）。

bigint 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
//bigint
#ifndef BIGINT
#define BIGINT
#define BASE 10000ll
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cmath>
#include<vector>
constexpr double PI2=6.283185307179586231995927;
struct complex{
    double real,imag;
    complex(double real=0,double imag=0):real(real),imag(imag){}
    complex operator+(const complex &x)const{return complex(real+x.real,imag+x.imag);}
    complex operator-(const complex &x)const{return complex(real-x.real,imag-x.imag);}
    complex operator*(const complex &x)const{return complex(real*x.real-imag*x.imag,real*x.imag+x.real*imag);}
};
complex omega[(1<<21)+10];
template<size_t Size>
class bigint{
private:
    inline void init_omega(int n){
        for(int i=1;i<=n;i<<=1)
            for(int j=0;j<(i>>1);j++){
                double arg=PI2*j/i;
                omega[(i>>1)+j]=complex(cos(arg),sin(arg));
            }
    }
    inline void FFT(std::vector<complex> &a,int n,bool inv){
        for(int i=0,j=0;i<n;i++){
            if(i<j) std::swap(a[i],a[j]);
            for(int l=n>>1;(j^=l)<l;l>>=1);
        }
        for(int len=2;len<=n;len<<=1)
            for(int i=0;i<n;i+=len)
                for(int j=0;j<(len>>1);j++){
                    complex w=inv?complex(omega[(len>>1)+j].real,-omega[(len>>1)+j].imag):omega[(len>>1)+j];
                    complex x=a[i+j],y=a[i+j+(len>>1)]*w;
                    a[i+j]=x+y,a[i+j+(len>>1)]=x-y;
                }
        if(inv) for(int i=0;i<n;i++) a[i].real/=n;
    }
    int len=1;
    int num[Size];
    inline void init(){
        memset(num,0,sizeof(int)*(len+2));
        len=1;
    }
public:
    bigint(){
        memset(num,0,sizeof(num));
        len=1;
    }
    template<typename T>
    bigint(const T &x){*this=x;}
    friend std::ostream &operator<<(std::ostream &out,const bigint &x){
        if(x.num[0]) out<<'-';
        out<<x.num[x.len];
        for(int i=x.len-1;i;i--)
            out<<std::setw(4)<<std::setfill('0')<<x.num[i];
        return out;
    }
    friend std::istream &operator>>(std::istream &in,bigint &x){
        std::string s;
        in>>s;x=s;
        return in;
    }
    template<typename T>
    bigint &operator=(const T &a){
        init();
        T x=a;
        if(x<0) num[0]=1,x=~x+1;
        len=0;
        while(x){
            num[++len]=x%BASE;
            x/=BASE;
        }
        return *this;
    }
    bigint &operator=(const std::string &a);
    bool operator<(const bigint &a)const{
        if(num[0]!=a.num[0]) return num[0]>a.num[0];
        if(len!=a.len) return num[0]?len>a.len:len<a.len;
        for(int i=len;i;i--)
            if(num[i]!=a.num[i])
                return num[0]?num[i]>a.num[i]:num[i]<a.num[i];
        return false;
    }
    bool operator>(const bigint &a)const{
        if(num[0]!=a.num[0]) return num[0]<a.num[0];
        if(len!=a.len) return num[0]?len<a.len:len>a.len;
        for(int i=len;i;i--)
            if(num[i]!=a.num[i])
                return num[0]?num[i]<a.num[i]:num[i]>a.num[i];
        return false;
    }
    bool operator<=(const bigint &a)const{
        if(num[0]!=a.num[0]) return num[0]>a.num[0];
        if(len!=a.len) return num[0]?len>a.len:len<a.len;
        for(int i=len;i;i--)
            if(num[i]!=a.num[i])
                return num[0]?num[i]>a.num[i]:num[i]<a.num[i];
        return true;
    }
    bool operator>=(const bigint &a)const{
        if(num[0]!=a.num[0]) return num[0]<a.num[0];
        if(len!=a.len) return num[0]?len<a.len:len>a.len;
        for(int i=len;i;i--)
            if(num[i]!=a.num[i])
                return num[0]?num[i]<a.num[i]:num[i]>a.num[i];
        return true;
    }
    bool operator==(const bigint &a)const{
        if(len!=a.len) return false;
        for(int i=0;i<=len;i++)
            if(num[i]!=a.num[i])
                return false;
        return true;
    }
    bool operator!=(const bigint &a)const{
        if(len!=a.len) return true;
        for(int i=0;i<=len;i++)
            if(num[i]!=a.num[i])
                return true;
        return false;
    }
    bigint &operator+=(const bigint &a){
        if(num[0]==a.num[0]){
            long long temp=0;
            int old_len=len;
            len=std::max(len,a.len);
            for(int i=1;i<=len;i++){
                long long sum=temp;
                if(i<=old_len) sum+=num[i];
                if(i<=a.len) sum+=a.num[i];
                num[i]=(int)(sum%BASE);
                temp=sum/BASE;
            }
            if(temp)
                num[++len]=temp;
        }
        else{
            bool this_large=this->abs()>=a.abs();
            const bigint &larger=this_large?*this:a;
            const bigint &smaller=this_large?a:*this;
            int new_len=larger.len;
            long long temp=0;
            for(int i=1;i<=new_len;i++){
                long long diff=(long long)larger.num[i]-temp;
                if(i<=smaller.len) diff-=smaller.num[i];
                if(diff<0){
                    diff+=BASE;
                    temp=1;
                }
                else temp=0;
                num[i]=diff;
            }
            len=new_len;
            while(len>1&&num[len]==0) len--;
            num[0]=this_large?num[0]:a.num[0];
            if(len==1&&num[1]==0) num[0]=0;
        }
        return *this;
    }
    bigint &operator-=(const bigint &a){
        bigint temp=a;
        temp.num[0]^=1;
        return *this+=temp;
    }
    bigint &operator*=(const bigint &a){
        if((len==1&&num[1]==0)||(a.len==1&&a.num[1]==0)){
            init();
            return *this;
        }
        int old_len=len;
        int old_num[Size];
        memcpy(old_num,num,sizeof(int)*(len+10));
        init();
        num[0]=old_num[0]^a.num[0];
        int len_sum=1;
        while(len_sum<old_len+a.len)
            len_sum<<=1;
        std::vector<complex> fa(len_sum+10),fb(len_sum+10);
        for(int i=0;i<old_len;i++)
            fa[i]=complex((double)old_num[i+1],0);
        for(int i=0;i<a.len;i++)
            fb[i]=complex((double)a.num[i+1],0);
        init_omega(len_sum);
        FFT(fa,len_sum,false);
        FFT(fb,len_sum,false);
        for(int i=0;i<len_sum;i++)
            fa[i]=fa[i]*fb[i];
        FFT(fa,len_sum,true);
        len=old_len+a.len;
        long long temp=0;
        for(int i=0;i<len;i++){
            long long val=(long long)round(fa[i].real)+temp;
            num[i+1]=(int)(val%BASE);
            temp=val/BASE;
        }
        if(temp) num[++len]=temp;
        while(len>1&&num[len]==0) len--;
        return *this;
    }
    bigint &operator++(){
        *this+=bigint(1);
        return *this;
    }
    bigint &operator--(){
        *this-=1;
        return *this;
    }
    template<typename T>
    bigint operator++(T){
        bigint res=*this;
        ++*this;
        return res;
    }
    template<typename T>
    bigint operator--(T){
        bigint res=*this;
        --*this;
        return res;
    }
    friend bigint operator+(const bigint &a,const bigint &b){return bigint(a)+=b;}
    friend bigint operator-(const bigint &a,const bigint &b){return bigint(a)-=b;}
    friend bigint operator*(const bigint &a,const bigint &b){return bigint(a)*=b;}
    bigint abs()const{
        bigint res=*this;
        res.num[0]=0;
        return res;
    }
};
template<size_t Size>
bigint<Size> &bigint<Size>::operator=(const std::string &a){
    init();
    int f=0;
    int slen=a.length();
    if(slen>0&&a[0]=='-') num[0]=f=1;
    len=0;
    int temp=0,w=1;
    for(int i=slen-1;i>=f;i--){
        temp+=(a[i]^48)*w;
        w=(w<<1)+(w<<3);
        if(w==BASE||i==f){
            num[++len]=(int)temp;
            temp=0;
            w=1;
        }
    }
    if(temp||len==0) num[++len]=temp;
    return *this;
}
#undef BASE
#endif

使用说明

前言

这份高精度模板使用压位实现常数优化，实现过程中为了保证乘法运算的精度，最终选择了压 $4$ 位，可以保证 $10^{1000000}$ 以内的精度。

声明

1
2
bigint</*length_of_number*/> a;
//因为压位，所以可以只开四分之一大小，但一般建议开大些

无需任何命名空间。

I/O 方式

为方便使用，接入了 iostream 的 I/O。

1
2
3
bigint<114514> a;
std::cin>>a;
std::cout<<a;

数值运算符

加法与减法使用 $O(n)$ 算法，乘法使用 $O(n\log n)$ 算法（FFT），也写了一份 NTT 实现，实测表现优于 FFT，但暂无法处理较大的数。

1
2
3
4
5
6
7
8
9
10
11
bigint<114514> a,b;
a+b;
a-b;
a*b;
a+=b;
a-=b;
a*=b;
a++;
a--;
++a;
--a;

赋值运算符

支持所有整形，同时对 std::string 进行特化，支持将一个格式符合正常数字的 std::string 转为高精度整形。

1
2
3
4
5
bigint<114514> a,b;
std::string c;
c="-1919810";
a=-1919810,b=c;
//a和b所存的值均为-1919810

关系符

除三路比较运算符（C++20）外的所有常用大小关系符。

1
2
3
4
bigint<114514> a=10,b=20;
a<b;//此表达式为true
a!=b;//此表达式为true
a==b;//此表达式为false

其他

成员函数 abs()，以 bigint 类型返回该数的绝对值。

关于 FFT/NTT 与压位对于高精度乘法的性能优化比对数据

data（洛谷 P1919 #1 数据）
code

1
2
3
4
5
6
7
8
9
10
11
//...
using namespace std;
bigint<2145141> a,b;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
    cin>>a>>b;
    cout<<a*b;
    return 0;
}

数据取 $5$ 次运行平均值。
评测环境：S2 四机房（Intel(R) Core(TM) i5-10400 CPU @ 2.90GHz 2.90 GHz）。MinGW-W64 GCC 11.4.0 64-bit Debug。
编译选项：
1
-std=c++14 -O2 -Wl,--stack=268435456

| | FFT | NTT |
| :——————: | :——————: | :——————: |
| 不压位 | 0.5712 | 0.5112 |
| 压 $2$ 位 | 0.2718 | - |
| 压 $4$ 位 | 0.1546 | - |

单位：$\text{s}$。
数据来自 RedPandaIDE 程序运行窗口自带的用时显示，真实评测时用时应会比表中数据略小。
单模数 NTT 压 $2$ 位/$4$ 位在数据范围内无法得到正确答案。

Upd

v1.1：增加了 NTT 命名空间，但因为一些原因暂不使用。
v1.2：改了改码风。
v1.3：使用 C++ 标准库中的 std::complex 代替手写的复数类。修复了初始化错误的问题。
v1.4：std::complex 跑的太慢啦，换回手写的复数类。
v1.5：改用预处理单位根计算，提高了精度。现在可以压 $4$ 位啦，效率大提升！