高精度模板

来贴一波学长写的模板

感觉写的很好，对于我这种不会用指针的蒟蒻来说，通熟易懂，网上很多模板都有指针，看到都头皮发麻QAQ

关于为什么不自己写，额，应该是太菜了QAQ

下面请见代码

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
256
257
258
259
260
261
262
263
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <queue>
#include <stack>
#include <vector>
#include <cmath>
#include <string>
#include <map>
#define N 1000001
#define M 50001
#define INF 1000000000
#define lowbit(x) (x&(-x))
#define repg(i,x) for(int i=cur[x];i;i=e[i].nt)
#define rep(i,x,y) for(int i=x;i<=y;i++)
#define pi acos(-1)
#define pb(x) push_back(x)
#define eps 1e-8
#define m(x) x.m
using namespace std;
typedef long long LL;
typedef pair<int,int>pa;
int n;
/*
本模板包括：
1.赋值运算，支持整数以及string类赋值，用法：a=b
2.基本运算，包括加减乘除取模，对单精度以及对高精度都有。
3.比较函数，>,<,<=,>=,==,!=。
4.外部函数包括最小公倍数，最大公约数，快速幂。 
仅支持10进制（不会打压位QAQ） 
UPD1:高精度是可以用vector优化内存的，我不会打QAQ 
UPD2:最好把高精度封装到结构体里面，实际使用时，
也不一定下面的要全打，要用什么打什么就行了 
UPD3:看上去好麻烦，实际上，这么封装之后，你
调用的时候就变的十分简单，不仅可以直接像整数一样
直接运算，而且queue,stack等STL也能使用。
UPD4:注意实际使用的时候高精度要放在前面
例如:aa*10，而不是10*aa 
UPD5:学会这类板子怎么打，日后矩阵之类的就好办 
"const"表示在这个函数中，调用的参数是不可改变的。 
*/
struct bign{
    long long num[510];int len; 
    void print(){//输出这个数 
        for(int i=len;i>=1;i--)printf("%lld",num[i]);printf("\n");
    }
    //定义赋值 
    bign(){}
    bign(string aa){*this=aa;}
    bign(long long aa){*this=aa;}//声明赋值函数 
    bign operator =(string aa){//string类赋值 
        memset(num,0,sizeof(num));
        len=aa.length();
        for(int i=0;i<len;i++)num[i+1]=aa[len-i-1]-'0';
        return *this;
    }
    bign operator =(long long aa){//整数类赋值 
        memset(num,0,sizeof(num));len=0;
        long long a=aa;
        if(!a)len++;
        while(a){
            num[++len]=a%10;a/=10;
        }
        return *this;
    }
    //比较函数 
    bool operator <(const bign& a)const{
        if(a.len>len)return true;
        else if(a.len<len)return false;
        for(int i=len;i>=1;i--){
            if(a.num[i]>num[i])return true;
            else if(a.num[i]<num[i])return false;
        }
        return false;
    }
    bool operator >(const bign& a)const{
        if(a.len<len)return true;
        else if(a.len>len)return false;
        for(int i=len;i>=1;i--){
            if(a.num[i]<num[i])return true;
            else if(a.num[i]>num[i])return false;
        }
        return false;
    }
    bool operator ==(const bign& a)const{
        if(a.len!=len)return false;
        for(int i=len;i>=1;i--){
            if(num[i]!=a.num[i])return false;
        }
        return true;
    }
    bool operator <=(const bign& a)const{return *this<a||*this==a;}
    bool operator >=(const bign& a)const{return *this>a||*this==a;}
    bool operator !=(const bign& a)const{return !(*this==a);}
    //进位以及退位 
    void carry(){
        for(int i=1;i<len;i++){num[i+1]+=num[i]/10;num[i]%=10;}
        while(num[len]>=10){num[len+1]+=num[len]/10;num[len]%=10;len++;}
    }
    void decomposition(){
        for(int i=1;i<len;i++)
        if(num[i]<0){
        num[i+1]--;
        num[i]+=10;
        }
        while(!num[len]&&len)len--;
        if(!len)*this=0;
    }
     
    //加法
    bign operator +(const long long& x)const{//高精度加整数 
        bign c;c=*this;
        c.num[1]+=x;
        c.carry();
        return c;
    }
    bign operator +=(const long long& x){
        *this=*this+x;return *this;
    }
    bign operator +(const bign& x)const{//高精度加高精度 
        bign c=*this; 
        c.len=max(len,x.len);
        for(int i=1;i<=c.len;i++)c.num[i]+=x.num[i];
        c.carry();
        return c;
    }
    bign operator +=(const bign& x){
        *this=*this+x;return *this;
    }
    //减法 
    bign operator -(const long long& x)const{//高精度减整数 
        bign c=*this;
        c.num[1]-=x;
        c.decomposition();
        return c;
    }
    bign operator -=(const long long& x){ 
        *this=*this-x;return *this;
    }
    bign operator -(const bign& x)const{//高精度减高精度
        bign c=*this;
        c.len=max(len,x.len);
        for(int i=1;i<=c.len;i++)c.num[i]-=x.num[i];
        c.decomposition();
        return c;
    }
    bign operator -=(const bign& x){
        *this=*this-x;return *this;
    }
    //乘法 
    bign operator *(const long long &x)const{//高精度乘整数 
        bign c=*this;
        for(int i=1;i<=len;i++)c.num[i]*=x;
        c.carry();
        return c;
    }
    bign operator *=(const long long& x){
        *this=*this*x;return *this;
    }
    bign operator *(const bign x)const{//高精度乘高精度 
        bign c=0;
        for(int i=1;i<=len;i++){
            for(int j=1;j<=x.len;j++)c.num[i+j-1]+=num[i]*x.num[j];
        }
        c.len=200;
        while(!c.num[c.len]&&c.len>1)c.len--;
        c.carry();
        return c;
    }
    bign operator *=(const bign& x){
        *this=*this*x;return *this;
    }
    //除法 
    bign operator /(const long long& x){//高精度除整数 
        bign c=0;
        long long now=0;
        for(int i=len;i>=1;i--){
            now=now*10+num[i];
            c.num[i]=now/x;now%=x;
        }c.len=len;
        c.decomposition();
        return c;
    }
    bign operator /=(const long long& x){
        *this=*this/x;return *this;
    }
    bign operator /(const bign& x)const{//高精度除高精度 
        bign a=0,rtn=0;
        for(int i=len;i>=1;i--){
            a=a*10+num[i];int cnt=0;
            while(a>=x){
                a-=x;cnt++;
            }
            rtn.num[i]=cnt;
        }rtn.len=len;
        rtn.decomposition();
        return rtn;
    }
    bign operator /=(const bign& x){
        *this=*this/x;return *this;
    }
    //取模 
    bign operator %(const long long& x)const{//高精度取模整数 
        long long now=0;
        for(int i=len;i>=1;i--){
            now=now*10+num[i];
            now%=x;
        }
        return bign(now);
    }
    bign operator %=(const long long& x){
        *this=*this%x;return *this;
    }
    bign operator %(const bign& x)const{//高精度取模高精度 
        bign a=0;
        for(int i=len;i>=1;i--){
            a=a*10+num[i];
            while(a>=x)a-=x;
        }
        return a;
    }
    bign operator %=(const bign& x){
        *this=*this%x;return *this;
    }
}f[110];
 
bign gcd(bign x,bign y){//最大公约数 
    if(y==bign(0))return x;
    else return gcd(y,x%y);
}
 
bign lcm(bign x,bign y){//最小公倍数 
    if(x<0)x*=-1;if(y<0)y*=-1;
    bign c=x*y;
    return c/gcd(x,y);
}
 
bign sqrt(bign x){//开方 
    x.len+=x.len%2;
    bign now=0,last=0;
    for(int i=x.len;i;i-=2){
        now=now*100+x.num[i]*10+x.num[i-1];
        int cnt=0;bign tmp=0;
        while(tmp+last*20+cnt*2+1<=now){
            tmp+=last*20+cnt*2+1;cnt++;
        }
        now-=tmp;last=last*10+cnt;
    }
    return last;
}
int main()
{
#ifdef WK
    freopen("D:\\in.txt","r",stdin);
    freopen("D:\\out.txt","w",stdout);
#endif
    f[1]=1;
    for(int i=2;i<=100;i++)f[i]=f[i-1]*3-f[i-2]+2;
    while(scanf("%d",&n)!=EOF)f[n].print();
    return 0;
}

赏

×

纯属好玩

扫码支持
扫码打赏，你说多少就多少

打开支付宝扫一扫，即可进行扫码打赏哦

本文标题:高精度模板

文章作者:Tyw_ei

发布时间:2017年08月17日 - 22时39分

最后更新:2017年08月24日 - 09时23分

原始链接:https://dextertyw.github.io/2017/08/17/高精度模板/

许可协议: "署名-非商用-相同方式共享 3.0" 转载请保留原文链接及作者。

文章目录
,