高精度

业界毒瘤
python大法好(雾

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
#define rad 10000
#define B 4//int压4位

struct Bi{
int s[2005],l;
Bi(){memset(s,0,sizeof(s));l=1;}//这里的memset可能会T……
};

Bi operator + (Bi a,Bi b){
a.l=a.l>b.l?a.l:b.l;
for(int i=1;i<=a.l;i++){
a.s[i]+=b.s[i];
if(a.s[i]>=rad) a.s[i]-=rad,a.s[i+1]++;
}
if(a.s[a.l+1]) a.l++;
return a;
}

Bi operator - (Bi a,Bi b){//大减小
for(int i=1;i<=a.l;i++){
a.s[i]-=b.s[i];
if(a.s[i]<0) a.s[i]+=rad,a.s[i+1]--;
}
while(a.l>1&&!a.s[a.l]) a.l--;
return a;
}

Bi operator * (Bi a,Bi b){//暴力
Bi c;c.l=a.l+b.l-1;
for(int i=1;i<=a.l;i++)
for(int j=1;j<=b.l;j++)
c.s[i+j-1]+=a.s[i]*b.s[j];
for(int i=1;i<=c.l;i++){
c.s[i+1]+=c.s[i]/rad;
c.s[i]%=rad;
}
if(c.s[c.l+1]) c.l++;
return c;
}

Bi operator / (Bi a,int b)
{
Bi c;c.l=a.l;int k=0;
for(int i=a.l;i>=1;i--){
k=k*rad+a.s[i];
c.s[i]=k/b;k%=b;
}
while(c.l>1&&!c.s[c.l]) c.l--;
return c;
}

bool operator < (Bi x,Bi y){
if(x.l!=y.l) return x.l<y.l;
for(int i=x.l;i>=1;i--)
if(x.s[i]!=y.s[i]) return x.s[i]<y.s[i];
return false;
}

void read(Bi &x)
{
int i,j;
scanf("%s",d+1);
int l=strlen(d+1);
for(i=1;i<=l;i++)
j=(l-i+B)/B,x.s[j]=x.s[j]*10+d[i]-'0';
x.l=(l-1+B)/B;
}

void print(Bi a){printf("%d",a.s[a.l]);for(int i=a.l-1;i;i--) printf("%04d",a.s[i]);}//补0输出
分享到: