关于C++高精度运算的几种方式

今天刚好写到了一题需要高精的题,查题解时看到了 __int64 ,想来想去就决定复习一下高精度运算了~~~


传统数组模拟加减乘除法运算( noip 常见算法)

传统数组高精,实际上就是模拟人类在草稿纸上笔算的过程。(如果你是数学大佬,那我告辞)

高精度加法

直接附代码了(下面都是)

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
#include <iostream> 
#include <cstdio>
#include <cstring>
using namespace std;
int main()
{
char a1[600],b1[600];
int a[600],b[600],c[600],lena,lenb,lenc,i,x;
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
memset(c,0,sizeof(c));
cin>>a1>>b1;
lena=strlen(a1);
lenb=strlen(b1);
for(i=0;i<=lena-1;i++)
a[lena-i]=a1[i]-48;
for(i=0;i<=lenb-1;i++)
b[lenb-i]=b1[i]-48;
lenc=1;
x=0;
while(lenc<=lena||lenc<=lenb)
{
c[lenc]=a[lenc]+b[lenc]+x;
x=c[lenc]/10;
c[lenc]%=10;
lenc++;
}
c[lenc]=x;
if(c[lenc]==0)
lenc--;
for(i=lenc;i>=1;i--)
cout<<c[i];
cout<<endl;
return 0;
}

高精度减法

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
#include <iostream> 
#include <cstdio>
#include <cstring>
using namespace std;
int main()
{
char n[100],a1[100],b1[100];
int a[100],b[100],c[100],lena,lenb,lenc,i,x;
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
memset(c,0,sizeof(c));
gets(a1);
gets(b1);
if(strlen(a1)<strlen(b1)||(strlen(a1)==strlen(b1)&&strcmp(a1,b1)<0))
{
strcpy(n,a1);
strcpy(a1,b1);
strcpy(b1,n);
cout<<"-";
}
lena=strlen(a1);
lenb=strlen(b1);
for(i=0;i<=lena-1;i++)
a[lena-i]=a1[i]-48;
for(i=0;i<=lenb-1;i++)
b[lenb-i]=b1[i]-48;
lenc=1;
while(lenc<=lena||lenc<=lenb)
{
if(a[lenc]<b[lenc])
{
a[lenc]+=10;
a[lenc+1]--;
}
c[lenc]=a[lenc]-b[lenc];
lenc++;
}
while((c[lenc]==0)&&(lenc>1))
lenc--;
for(i=lenc;i>=1;i--)
cout<<c[i];
cout<<endl;
return 0;
}

高精度乘法

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
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int main()
{
char a1[2002],b1[2002];
int a[2002],b[2002],c[4002],lena,lenb,lenc,i,j,x;
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
memset(c,0,sizeof(c));
cin>>a1>>b1;
lena=strlen(a1);
lenb=strlen(b1);
for(i=0;i<=lena-1;i++)
a[lena-i]=a1[i]-48;
for(i=0;i<=lenb-1;i++)
b[lenb-i]=b1[i]-48;
for(i=1;i<=lena;i++)
{
x=0;
for(j=1;j<=lenb;j++)
{
c[i+j-1]=a[i]*b[j]+x+c[i+j-1];
x=c[i+j-1]/10;
c[i+j-1]%=10;
}
c[i+lenb]=x;
}
lenc=lena+lenb;
while(c[lenc]==0&&lenc>1)
lenc--;
for(i=lenc;i>=1;i--)
cout<<c[i];
cout<<endl;
return 0;
}

高精度除法

高精除低精

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
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int main()
{
char a1[100],c1[100];
int a[100],c[100],lena,i,x=0,lenc,b;
memset(a,0,sizeof(a));
memset(c,0,sizeof(c));
gets(a1);
cin>>b;
lena=strlen(a1);
for(i=0;i<=lena-1;i++)
a[i+1]=a1[i]-48;
for(i=0;i<=lena;i++)
{
c[i]=(x*10+a[i])/b;
x=(x*10+a[i])%b;
}
lenc=1;
while(c[lenc]==0&&lenc<lena)
lenc++;
for(i=lenc;i<=lena;i++)
cout<<c[i];
cout<<endl;
return 0;
}

高精除高精

这个复杂一点,要用到前面的好几种高精度运算

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
#include <iostream>
#include <cstring>
using namespace std;
int a[101],b[101],c[101],d,i;

//--------------------------------------

void init(int a[])
{
string s;
cin>>s;
a[0]=s.length();
for(i=1;i<=a[0];i++)
a[i]=s[a[0]-i]-48;
}

//--------------------------------------

void print(int a[])
{
int i;
if(a[0]==0)
{
cout<<0<<endl;
return;
}
for(i=a[0];i>0;i--)
cout<<a[i];
cout<<endl;
return;
}

//-------------------------------------

int cmp(int a[],int b[])
{
int i;
if(a[0]>b[0])
return 1;
if(a[0]<b[0])
return -1;
for(i=a[0];i>0;i--)
{
if(a[i]>b[i])
return 1;
if(a[i]<b[i])
return -1;
}
return 0;
}

//-------------------------------------

void jian(int a[],int b[])
{
int flag,i;
flag=cmp(a,b);
if(flag==0)
{
a[0]=0;
return;
}
if(flag==1)
{
for(i=1;i<=a[0];i++)
{
if(a[i]<b[i])
{
a[i+1]--;
a[i]+=10;
}
a[i]-=b[i];
}
while(a[0]>0&&a[a[0]]==0)
a[0]--;
return;
}
}

//------------------------------------

void numcpy(int p[],int q[],int det)
{
for(int i=1;i<=p[0];i++)
q[i+det-1]=p[i];
q[0]=p[0]+det-1;
}

//------------------------------------

void chugao(int a[],int b[],int c[])
{
int i,tmp[101];
c[0]=a[0]-b[0]+1;
for(i=c[0];i>0;i--)
{
memset(tmp,0,sizeof(tmp));
numcpy(b,tmp,i);
while(cmp(a,tmp)>=0)
{
c[i]++;
jian(a,tmp);
}
}
while(c[0]>0&&c[c[0]]==0)
c[0]--;
return;
}

//------------------------------------

int main()
{
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
memset(c,0,sizeof(c));
init(a);
init(b);
chugao(a,b,c);
print(c);
print(a);
return 0;
}

高精乘方

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
#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
void change(int m,char a[]) //数字转化为字符串存储
{
int t=m;
for(int i=0; t;i++){
a[i]=t%10+48;
t/=10;
}
}
void reverse(char str[],int l) //字符串翻转
{
char temp;
for(int i=0;i<=l/2;i++)
{
temp=str[i];
str[i]=str[l-i];
str[l-i]=temp;
}
}
void mul(int m,int n,char result[]) //高精度m^n 乘法
{
char a[20]={0};
int c[5000]={0};
int la,lr;
if(n==0 || m==1){result[0]='1';return ;}
change(m,a); //将数字转化为字符
la=strlen(a)-1; //记录字符a 的位数
lr=la;
strcpy(result,a); //积初始化为a*1
int i,j,k,l;
for(i=2;i<=n;i++){ //result*=a^(n-1)
memset(c,0,sizeof(c));
for(j=0;j<=la;j++) //大数相乘
for(k=0;k<=lr;k++){
c[j+k]+=(a[j]-48)*(result[k]-48);
c[j+k+1]+=c[j+k]/10;

c[j+k]%=10;
}
l=k+j+1; //记录当前可能的最大位数
while(c[l]==0)l--; //去除la+lr+1 最高几位的的0
memset(result,0,sizeof(result));
for(j=0;j<=l;j++)result[j]=c[j]+'0';//将临时变量c 里的数字转化为字符存到result 中
lr=l; //刷新result 的字符个数
}
reverse(result,lr); //字符串翻转,方便输出
}
int main()
{
int m,n;
while(scanf("%d%d",&m,&n),m&&n)
{
char result[5000]={0}; // 这句必须放到循环体内,WA得好苦 因为有这句
if(n==0 ||m==1) result[0]='1';
mul(m,n,result);
printf("%s\n",result);
}
return 0;
}

高精度取模

这个就十分简单了,都不用记录商

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std;
string s;
long long k=0,a,b,i;
bool flag;
int main()
{
cin>>s>>b;//输入被除数和除数
for(int i=0;i<s.size();i++)//从高位开始,一位一位向低位
{
a=a*10+s[i]-'0';//加上被除数的这一位
a%=b;//一直取余
}
cout<<a;
return 0;
}

当然还有大佬用的重载运算符操作

这个东西我就真的不会了

直接上个实例吧

高精度的GCD(最大公约数)

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
#include <cstdio>
#include <cstring>
#include <algorithm>
#define rep(i,l,r) for (int i=l;i<=r;++i)
const int Mx=1252,MOD=100000000;
struct BIGN{
int a[Mx+10];
BIGN(){memset(a,0,sizeof a);}
int &operator [](int i){return a[i];}
void operator /=(int x){ //高精 '/='
for (int i=Mx;i>=1;--i)
a[i-1]+=a[i]%x*MOD,a[i]/=x;
}
void operator -=(BIGN &b){ //高精 '-='
for (int i=1;i<Mx;++i)
a[i]=a[i]-b[i]+(a[i-1]+MOD)/MOD -1,a[i-1]=(a[i-1]+MOD)%MOD;
}
void operator *=(int x){ //高精 '*='
for (int i=1;i<Mx;++i)
a[i]=a[i]*x+a[i-1]/MOD,a[i-1]%=MOD;
}
bool operator <(BIGN &b){ //重定义 '<'
for (int i=Mx;i>=1;--i)
if (a[i]!=b[i]) return a[i]<b[i];
return false;
}
bool iszero(){ //判0
for (int i=1;i<Mx;++i) if (a[i]!=0) return false;
return true;
}
void read(){
char tp[10005]={'0','0','0','0','0','0','0','0'};
scanf("%s",tp+8);
int len=strlen(tp+1),p=1;
while (len-8*p+1>0)
scanf(tp+len-8*p+++1,"%8d",&a[p]);
}
void print(){
int p=Mx;
while (!a[p]&&p>0) p--;
printf("%d",a[p--]);
while (p>0) printf("%08d",a[p--]);
printf("\n");
}
};
BIGN gcd(BIGN x,BIGN y){
int g=0;bool x1,y1;
while (!x.iszero() && !y.iszero()){
x1=!(x[1]&1),y1=!(y[1]&1);
if (x1 && y1){g++;x/=2,y/=2;}else
if (x1 || y1){if (x1) x/=2;else y/=2;}else
if (y<x) x-=y;else y-=x;
}
if (x<y) x=y;
while (g--) x*=2;
return x;
}
BIGN a,b;
int main(){
a.read();
b.read();
gcd(a,b).print();
}

懒人专用 __int64

其实是上面第一种忘得差不多了,第二种还不会

不过针对 GCCVC ,这个东西是有差别的

主要是输入啦

VC6.0 的 64 位整数分别叫做 __int64unsigned __int64 ,其范围分别是[-2^63, 2^63)与[0,2^64),即 -9223372036854775808 ~ 9223372036854775807 与 0 ~ 18446744073709551615 (约 1800 亿亿)。对 64 位整数的运算与 32 位整数基本相同,都支持四则运算与位运算等。当进行 64 位与 32 位的混合运算时, 32 位整数会被隐式转换成 64 位整数。但是, VC 的输入输出与 __int64 的兼容就不是很好了,如果你写下这样一段代码:

1
2
3
__int64 a;
cin>>a;
cout<<a;

那么,在第2行会收到“ error C2679: binary '>>' : no operator defined which takes a right-hand operand of type '__int64' (or there is no acceptable conversion) ”的错误;在第3行会收到“ error C2593: 'operator <<' is ambiguous ”的错误。那是不是就不能进行输入输出呢?当然不是,你可以使用C的写法:

1
2
scanf("%I64d",&a);
printf("%I64d",a);

就可以正确输入输出了。当使用 unsigned __int64 时,把 "I64d" 改为 "I64u" 就可以了。

OJ 通常使用 g++ 编译器。其 64 位扩展方式与 VC 有所不同,它们分别叫做 long long 与 unsigned long long 。处理规模与除输入输出外的使用方法同上。对于输入输出,它的扩展比VC好。既可以使用

1
2
3
long long a;
cin>>a;
cout<<a;

也可以使用

1
2
scanf("%lld",&a);
printf("%lld",a);

使用无符号数时,将 "%lld" 改成 "%llu" 即可。
最后再说明两点点:

1、作为一个特例,如果你使用的是 Dev-C++ 的 g++ 编译器,它使用的是 “%I64d” 而非 “%lld” 。

2、注意: __int64 是两个短的下划线


最后补充一个 int128 和 uint128

PS:这玩意只有 Linux 可以用

定义方式 __int64 是一样的

1
__int128 a;

只是这玩意还不能用 cincout 进行读入读出( scanfprintf 也不行)

所幸现在的 oj 基本上都是 linux 系统的

所以只能抄一个读入读出代码了

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
#include <bits/stdc++.h>
using namespace std;
inline __int128 read(){
__int128 x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}

inline void print(__int128 x){
if(x<0){
putchar('-');
x=-x;
}
if(x>9)
print(x/10);
putchar(x%10+'0');
}

int main(void){
__int128 a = read();
__int128 b = read();
print(a + b);
cout<<endl;
return 0;
}

关于高精度的算法我知道的就这些了,当然你如果学的是 python

好吧,以上东西你不需要