关于C++高精度运算的几种方式
什么是高精度?
我们知道，C/C++在64位编译器中支持的环境下，其各种整型数据类型表示是有范围的：
尽管long long类型能表示的数已经相当大了，但和一些天文数字比起来，它连屏幕的一行都占不到。很多实际数学问题其实是long long也无法解决的。
例如，围棋的走法有3的361次方，这个数字怎么显示出来？宇宙中原子的总和是10的80次方，怎么显示出来？这些都是语言本身的数据类型无法表示的。实际上，这些数字如果用二进制去储存的话，需要的空间也是特别大的。为了节约空间，同时让我们能够算出这些大数据，我们需要一种应用数组进行模拟计算的方法——高精度计算。
传统数组模拟加减乘除法运算（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;
}如何进行高精度的加法？
回想小学数学，那一个个竖式，逢十进一，简便美观的十进制表达。
于是，高精度加法，其实就是基于竖式运算原理，正因如此，我们才需要对齐两个加数.
加法：
先获取两个加数中最大的位数len，则本次加法计算需要进行len次操作. 从第0位开始，每次将对应位相加，得到和在该位的数值. 如果和在该位的数值大于等于10，那么将其减掉10，并让高一位加1.
高精度减法：
#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;
}实现高精度减法，原理与加法相似，仍然是竖式原理：
先获取被减数的位数len，则本次减法计算需要进行len次操作. 从第0位开始，每次将对应位相减，得到和在该位的数值. 如果和在该位的数值小于0，那么将其加上10，并让高一位减1.
但是这样的减法是无法计算结果为负数的情况. 例如1 - 10。为了解决减法出现负数的问题，我们需要往输出中添加一个表示正负的符号. 例如，添加一个bool值，并定义一个比较函数，利用其比较被减数和减数的大小（此处比较函数就交给你们啦）. 当减数大于被减数，让设置的bool值为0，反之为1. 当bool值为1时直接进行减法运算. 如果bool值为0，就返回用减数减去被减数的结果.
高精度乘法： 要进行高精度乘法，我们会如何去操作？ 竖式乘法？我们很容易想到这样的方式： 计算123 * 52， 首先列竖式，让123乘以2，也就是让每一位乘以2，得到246. 然后让123每一位乘以5，得到615（这里隐含了进位操作）. 最后，因为5是十位，它的位权是10，所以615修正为6150. 让6150+246，得到结果6396. 这个算法是可行的，让我们来看它的步骤应该如何设计：
首先获取被乘数和乘数的长度len1，len2；
定义len2个高精度数
最后一步和自然的竖式乘法的最后一步一致，让所有的
#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;
}高精除高精：
高精度除法的原理仍然是基于竖式除法……只不过，为了方便代码更加容易理解，我们不妨换一种方式解释. 譬如，我们现在要计算1234除以9.
- 首先，获取最大位是4.将其减1得到3.
- 9乘以10的3次幂，得到9000.
- 用1234减去9000，结果小于0，有效的减法为0次. 在结果的千位放置0.
- 将9000降幂变为900，用1234减去900，得到334. 再减一个900，小于0. 有效的减法为1次，在结果的百位放置.
- 将900降幂得到90，用334减去90，可以减3次，得到64. 有效的减法为3次，在结果的十位放置3.
- 将90降幂得到9，用64减去9，可以减7次，得到1.在结果的个位放置7.
- 9已经是9乘以10的零次幂了，最后这个1小于除数，那么我们除法得到的余数是1.
那么，我们将其转化为可以被机器执行的描述：
- 如果被除数的位数（len1）小于除数的位数（len2），直接返回0. (余数为被除数.)
- 否则的话，获取除数位数，让其乘以10的（被除数位数-除数位数）次方，得到一个数b.
- 定义一个长度最长为被除数位数数组cnt[len1].
- 将被除数减去b. 每减去一次b，cnt[位数]++.
- 当被除数即将在减去后小于0时，不执行该步减法，让b缩小为原来的十分之一.
-
继续减，直到b和原来的除数相等.
#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; }
该算法的实现依赖于高精度乘法和高精度减法，只有这两种计算方法已经封装了才可以实现除法. 另外，同样需要一个比较函数.
利用这个算法，我们就可以求出两个数的商和余数了.
#### 高精取模：
```cpp
#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;
}高精乘方：
#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++){
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;
scanf("%d%d",&m,&n);
char result[5000]={0};
if(n==0 ||m==1) result[0]='1';
mul(m,n,result);
printf("%s\n",result);
return 0;
}高精度开根：
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
struct Int{
int arr[5005],len;//倒着存,一格四位,数组防爆稍微开大点
};
Int zero;
void empty(){//重置zero
memset(zero.arr,0,sizeof(zero.arr));
zero.len = 0;
}
Int input(char str[10005]){//把字符串变为Int类型数,很玄学
char revstr[10005];
Int ans = zero;
int len = strlen(str);
for(int i = 1;i <= len;i++){
revstr[i] = str[len - i];//先翻转
}
int use = 0,start = 1;
for(int i = 1;i <= len;i+=4){//存入所有完整的位
if((i + 3) > len){
break;
}
use++;//arr用的位数+1
ans.arr[use] = revstr[i] - '0' + (revstr[i + 1] - '0') * 10 + (revstr[i + 2] - '0') * 100 + (revstr[i + 3] - '0') * 1000;//这个自己推算一下
start += 4;//不完整第一位+4
}
if(len % 4 == 1){//存入不完整位
ans.arr[++use] = revstr[start] - '0';
}else if(len % 4 == 2){
ans.arr[++use] = revstr[start] - '0' + (revstr[start + 1] - '0') * 10;
}else if(len % 4 == 3){
ans.arr[++use] = revstr[start] - '0' + (revstr[start + 1] - '0') * 10 + (revstr[start + 2] - '0') * 100;
}
ans.len = use;
return ans;
}
Int plus(Int a,Int b){//加法运算
Int ans = zero;
int len = max(a.len,b.len);
for(int i = 1;i <= len;i++){
ans.arr[i] += a.arr[i] + b.arr[i];
ans.len = i;
if(ans.arr[i] > 9999){//用于进位
ans.arr[i + 1] += 1;
ans.len = i + 1;
ans.arr[i] -= 10000;
}
}
return ans;
}
Int reduce(Int a,Int b){//减法运算
Int ans = zero;
int len = max(a.len,b.len);
for(int i = 1;i <= len;i++){
ans.arr[i] += (a.arr[i] - b.arr[i]);
if(ans.arr[i] >= 0){
ans.len = i;
}
if(ans.arr[i] < 0){
ans.arr[i + 1] -= 1;
ans.arr[i] += 10000;
}
}
for(int i = ans.len;i >= 1;i--){//本来不需要这个循环,但是找不出错就加了一个
if(ans.arr[i] != 0){
ans.len = i;
break;
}
}
return ans;
}
Int mult(Int a,Int b){//乘法运算
Int ans = zero;
for(int i = 1;i <= a.len;i++){
for(int j = 1;j <= b.len;j++){
ans.arr[i + j - 1] += a.arr[i] * b.arr[j];
}
}
for(int i = 1;i <= a.len + b.len;i++){//超过9999的部分向前进位
if(ans.arr[i] > 9999){
ans.arr[i + 1] += ans.arr[i] / 10000;
ans.arr[i] = ans.arr[i] % 10000;
}
}
if(ans.arr[a.len + b.len] > 0){//多一位特判
ans.len = a.len + b.len;
}else{
ans.len = a.len + b.len - 1;
}
return ans;
}
Int division(Int a,long long b){//除法运算,只需要高精除以int就行了
if(b == 1){//加速
return a;
}
Int ans = zero;
long long left = 0;
for(int i = a.len;i >= 1;i--){
if((left * 10000 + a.arr[i]) >= b){//如果剩余 + 现在够除
ans.arr[i] = (left * 10000 + a.arr[i]) / b;
left = (left * 10000 + a.arr[i]) % b;//算出新剩余
if(i > ans.len){
ans.len = i;
}
}else{
left = left * 10000 + a.arr[i];//否则直接更新剩余
}
}
return ans;
}
void print(Int num){//输出函数,也很玄学
bool zero = false;//有没有出现过可以输出的数字
for(int i = num.len;i >= 1;i--){
if(i == num.len){//第一位不用补0
if(num.arr[i] != 0){
zero = true;
}
printf("%d",num.arr[i]);
continue;
}
if(zero == false && num.arr[i] == 0){//前导0直接跳过
continue;
}
if(num.arr[i] > 0){
zero = true;
}
if(num.arr[i] < 1000){
if(num.arr[i] >= 100){//>100补一个
printf("0");
}else if(num.arr[i] >= 10){//>10补两个
printf("00");
}else{
printf("000");//否则补3个
}
}
printf("%d",num.arr[i]);//输出自身(如果是0,刚好补3个 + 自己1个 = 4个0)
}
printf("\n");
}
int cmp(Int a,Int b){//比较函数,a > b返回1,a < b返回-1,a = b返回0
if(a.len > b.len){//位数不同直接返回
return 1;
}else if(a.len < b.len){
return -1;
}
for(int i = a.len;i >= 1;i--){//一位一位比较
if(a.arr[i] > b.arr[i]){
return 1;
}else if(a.arr[i] < b.arr[i]){
return -1;
}
}
return 0;
}
Int put(int k){//将int转换为Int的快捷函数
Int ans = zero;
ans.arr[1] = k;//第一位直接加k
ans.len = 1;
for(int i = 2;ans.arr[i - 1] > 9999;i++){//一位一位匀
ans.arr[i] = ans.arr[i-1] / 10000;
ans.arr[i-1] = ans.arr[i-1] % 10000;
ans.len = i;
}
return ans;
}
Int power(Int p,int k){//计算p ^ k的快速方法,参考P1226快速幂的题解
Int ans = put(1),x = p;
while(k != 1){
if(k % 2 == 1){
ans = mult(ans,x);
}
x = mult(x,x);
k = k / 2;
}
return mult(ans,x);
}
int main(){//超级玄学的主函数
empty();
char str1[10005];
int m;
scanf("%d %s",&m,str1);
Int k = input(str1);
Int left,right,mid;
memset(left.arr,0,sizeof(left.arr));
left.len = 0;
left.arr[1] = 1;
memset(right.arr,0,sizeof(right.arr));
right.len = 1;
right.arr[1] = 1;//清理left和right
while(cmp(power(right,m),k) == -1){//这里参考了erge大佬的说法,原文如下:
//你应该先将l赋为1，r赋为2 然后不停l=r，r*=2，看r^m是否>=n 找r上限 这样可以避免RE以及TLE
//还有一段无关的没复制,这是个缩小left和right的运算方法
left = right;
right = mult(right,put(2));
}
Int p = power(put(10),m);//最为玄学的地方来了!!
k = mult(k,p);//这里为了保证精度要多算1位,这样的话left和right要乘10,k要乘10 ^ m,下面讲了为什么
left = mult(left,put(10));//其他大佬貌似都没这样做,可能还是因为我太弱了
right = mult(right,put(10));
while(cmp(reduce(right,left),put(2)) != -1){//判断right-left的差是否小于2,如果改成1有的时候会死循环，但是由于写2精度可能不足,我就加了玄学的多算一位的方法
mid = division(plus(left,right),2);//计算left和right的平均数
int cmp1 = cmp(power(mid,m),k);//判断mid ^ m与k的大小
if(cmp1 == 1){//如果k > mid ^ m,right = mid
right = mid;
}else{//如果mid ^ m > k,left = mid
left = mid;
}
}
if(cmp(left,put(10)) == -1){//如果答案 < 10(真实答案 < 1),程序会不输出,所以要特判
printf("0\n");
}else{
print(division(left,10));//答案要除以10输出
}
}如果你看到这，你就可以去玩玩这题 了。
当然还有大佬用的重载运算符操作
这个东西我就真的不会了
直接上个实例吧
高精度的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 ，其范围分别是
__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" 即可。 最后再说明两点：
- 作为一个特例，如果你使用的是 Dev-C++ 的 g++ 编译器，它使用的是 “%I64d” 而非 “%lld” 。
- 注意： __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
好吧，以上东西你不需要