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

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

---

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

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

高精度加法

直接附代码了（下面都是）

#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;
}

高精度减法

#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; 
}

高精度乘法

#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;
} 

高精度除法

高精除低精

#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;
} 

高精除高精

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

#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;
}

高精乘方

#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;
}

高精度取模

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

#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（最大公约数）

#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

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

不过针对 GCC 和 VC ，这个东西是有差别的

主要是输入啦

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

__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的写法：

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

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

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

long long a;
cin>>a;
cout<<a;

也可以使用

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

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

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

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

---

最后补充一个 __int128 和 __uint128

PS：这玩意只有 Linux 可以用

定义方式 __int64 是一样的

__int128 a;

只是这玩意还不能用 cin 和 cout 进行读入读出（ scanf 和 printf 也不行）

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

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

#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

好吧，以上东西你不需要