高精度
高精度计算
————高精度加法是信息学的一种重要算法。这种算法使用多个存储单位进行计算，因此它的计算范围超过一般使用一个存储单位的算法。也是一些信息学竞赛的常考题目。
一、高精度计算要注意的几个问题
1.数据的接收方法和存储方法
高精度计算一般输入的数都较长，需要用字符串的方式读入，利用字符串函数和操作运算，将每一位数取出，转存到数组中。
2.进位，借位处理方法
- 加法进位
c[i]=a[i]+b[i];
if(c[i]>=10)
{
c[i]%=10; c[i]++;
}- 减法借位
if(a[i]<b[i])
{
a[i+1]--;a[i]+=10;
}
c[i]=a[i]-b[i];
- 乘法进位
c[i+j-1]=a[i]*b[j]+x+c[i+j-1];
x=c[i+j-1];
c[i+j-1]%=10;二、高精度程序
1.高精度加法
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char a1[1000],b1[1000];
int a[1000],b[1000],c[1000];
int main()
{
scanf("%s",a1);//读入两个字符串，为两个加数 。
scanf("%s",b1);//读入两个字符串，为两个加数 。
if(a1[0]==48&&b1[0]==48)//特判两个数均为零，以免前导0被删掉。
{
cout<<"0"<<endl;//如果两个数都为0，直接输出0。
return 0;
}
int lena=strlen(a1),lenb=strlen(b1);//lena为a的长度，lenb为b的长度。
for(int i=0; i<lena; i++)
{
a[lena-i-1]=int(a1[i]-48);//将a倒序并强制转换为数字，用整形数组存储，以便计算。
}
for(int i=0; i<lenb; i++)
{
b[lenb-i-1]=int(b1[i]-48);//将b倒序并强制转换为数字，用整形数组存储，以便计算。
}
int m=max(lena,lenb);//求a与b的最大长度。
for(int i=0; i<m; i++)
{
c[i]+=a[i]+b[i];//将a[i]+b[i]的值与前面的进位相加，赋给c[i]。
while(c[i]>=10)//加完当c[i]>10时要进位。
{
c[i+1]++;//加法进位 。
c[i]-=10;//加法进位 。
}
}
m++;
while(c[m]==0)
m--; //删除前导0。
for(int i=m; i>=0; i--)
cout<<c[i];//输出。
return 0;
}2.高精度减法
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int a[100000],b[100000],c[100000],lena,lenb,lenc,i;
int main()
{
char n[100000],n1[100000],n2[100000];
cin>>n1;//读入字符串n1，为被减数。
cin>>n2;//读入字符串n2，为减数。
if(strlen(n1)<strlen(n2)||((strlen(n1))==strlen(n2))&&(strcmp(n1,n2)<0))
{
strcpy(n,n1);
strcpy(n1,n2);
strcpy(n2,n);
cout<<"-";
}
/*比较减数与被减数大小关系。当减数位数小于被减数，或位数相等但减数小于被减数时输出，
负号("-")并把两个数交换，以便计算 。
*/
lena=strlen(n1);//lena为a的长度。
lenb=strlen(n2);//lenb为b的长度。
for(i=0; i<=lena-1; i++)
{
a[lena-i]=int (n1[i]-48);//将a倒序并强制转换为数字，用整形数组存储，以便计算。
}
for(i=0; i<=lenb-1; i++)
{
b[lenb-i]=int (n2[i]-48);//将b倒序并强制转换为数字，用整形数组存储，以便计算。
}
i=1;
while(i<=lena||i<lenb)//i小于任何一个数的长度时进行减法。
{
if(a[i]<b[i])
{
a[i]+=10;//减法借位 。
a[i+1]--;//减法借位。
}
c[i]=a[i]-b[i];
i++;
}
lenc=i;
while((c[lenc]==0)&&(lenc>1))
{
lenc--;//删除前导0。
}
for(i=lenc; i>=1; i--)
{
cout<<c[i];//输出。
}
return 0;
}3.高精度乘法
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int a[5000],b[5000],c[5000];
int la,lb,lc,i,j,n,ls,ii;
char s[5000];
int p;
int main()
{
while (scanf("%s %d",s,&n)!=EOF)//读入
{
ls=strlen(s);
for (p=0;p<ls;p++) if (s[p]=='.') break;//找到小数点的位置
la=0;
for (i=0;i<ls;i++)//丢掉小数点把所有的数倒序存在a数组中
{
if (s[ls-i-1]=='.') continue;
la++;
a[la]=s[ls-i-1]-'0';
}
p=(ls-1-p)*n;//求出小数点的位数
memcpy(c,a,sizeof(c));//把c数组赋值成a数组，因为n=1时不会算
//其实也有办法算的，可以把b数组搞成1，然后算一次，不过会慢点
lc=la;//c的长度
for (ii=2;ii<=n;ii++)//一次一次的乘
{
memcpy(b,c,sizeof(b));//把b数组赋值成c数组
memset(c,0,sizeof(c));
lb=lc;//位数
lc=la+lb;//位数加起来
for (i=1;i<=la;i++)//高精度乘法
{
for (j=1;j<=lb;j++)
{
c[i+j-1]+=a[i]*b[j];//先加进去
c[i+j]+=c[i+j-1]/10;//进位
c[i+j-1]%=10;//取模
}
}
while (c[lc]==0&&lc>p) lc--;
}
int a1,b1;//两个指针，丢掉首尾的0
a1=lc;
b1=1;
while (c[a1]==0&&a1>p) a1--;
while (c[b1]==0) b1++;
for (i=a1;i>=b1;i--)//正着输出
{
if (i==p) printf(".");//嗯小数点有p位，so
printf("%d",c[i]);
}
printf("\n");//记得换行
}
return 0;
}4.高精度小数幂
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int a[5000],b[5000],c[5000];
int la,lb,lc,i,j,n,ls,ii;
char s[5000];
int p;
int main()
{
while (scanf("%s %d",s,&n)!=EOF)//读入
{
ls=strlen(s);
for (p=0;p<ls;p++) if (s[p]=='.') break;//找到小数点的位置
la=0;
for (i=0;i<ls;i++)//丢掉小数点把所有的数倒序存在a数组中
{
if (s[ls-i-1]=='.') continue;
la++;
a[la]=s[ls-i-1]-'0';
}
p=(ls-1-p)*n;//求出小数点的位数
memcpy(c,a,sizeof(c));//把c数组赋值成a数组，因为n=1时不会算
//其实也有办法算的，可以把b数组搞成1，然后算一次，不过会慢点
lc=la;//c的长度
for (ii=2;ii<=n;ii++)//一次一次的乘
{
memcpy(b,c,sizeof(b));//把b数组赋值成c数组
memset(c,0,sizeof(c));
lb=lc;//位数
lc=la+lb;//位数加起来
for (i=1;i<=la;i++)//高精度乘法
{
for (j=1;j<=lb;j++)
{
c[i+j-1]+=a[i]*b[j];//先加进去
c[i+j]+=c[i+j-1]/10;//进位
c[i+j-1]%=10;//取模
}
}
while (c[lc]==0&&lc>p) lc--;
}
int a1,b1;//两个指针，丢掉首尾的0
a1=lc;
b1=1;
while (c[a1]==0&&a1>p) a1--;
while (c[b1]==0) b1++;
for (i=a1;i>=b1;i--)//正着输出
{
if (i==p) printf(".");//小数点有p位。
printf("%d",c[i]);
}
printf("\n");//记得换行
}
return 0;
}5.高精度开根号
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#define Ll unsigned long long
using namespace std;
const Ll NN=1e9;
const int N=9;
struct H
{
Ll a[1500],len;
H()
{
memset(a,0,sizeof a);
len=1;
}
};
int n;
H s;
void init(H &a) //读入
{
string s;
cin>>s;
int l;
a.len=0;
for(int r=s.length()-1; r>=0; r-=N)
{
a.len++;
if(r>=N-1)l=r-N+1;
else l=0;
for(int i=l; i<=r; i++)a.a[a.len]=a.a[a.len]*10+s[i]-48;
}
}
void outit(H a) //输出
{
printf("%d",a.a[a.len]);
for(int i=a.len-1; i; i--)
{
for(int k=NN/10; a.a[i]<k; k/=10)printf("0");
if(a.a[i])printf("%d",a.a[i]);
}
printf("\n");
}
void in(H &a,int x) //赋值
{
if(!x)return;
a.len=0;
while(x)
{
a.a[++a.len]=x%NN;
x=x/NN;
}
}
bool bigD(H a,H b) //比较是否大于等于
{
if(a.len>b.len)return 1;
if(a.len<b.len)return 0;
for(int i=a.len; i; i--)
if(a.a[i]!=b.a[i])
if(a.a[i]>b.a[i])return 1;
else return 0;
return 1;
}
H jia(H a,H b) //加法
{
H c;
int l=max(a.len,b.len);
for(int i=1; i<=l; i++)
{
c.a[i]+=a.a[i]+b.a[i];
c.a[i+1]=c.a[i]/NN;
c.a[i]%=NN;
}
if(c.a[l+1])l++;
c.len=l;
return c;
}
H chu(H a) //除法
{
H c;
if(a.len==1)
{
c.a[1]=a.a[1]>>1;
return c;
}
for(int i=a.len; i; i--)
{
if(a.a[i]&1ll)a.a[i-1]+=NN;
c.a[i]=a.a[i]>>1;
}
if(c.a[a.len])c.len=a.len;
else c.len=a.len-1;
return c;
}
H rrr(H a) //-1操作
{
if(a.len==1)
{
a.a[1]--;
return a;
}
H c=a;
c.a[1]--;
int l=1;
while(c.a[l]<0)
{
c.a[l]=NN-1;
c.a[++l]--;
}
if(!c.a[c.len])c.len--;
return c;
}
H chen(H a,H b) //乘法
{
H z;
z.len=a.len+b.len+2;
for(int i=1; i<=a.len; i++)
for(int j=1; j<=b.len; j++)z.a[i+j-1]+=(a.a[i]*b.a[j]);
for(int i=1; i<=z.len; i++)z.a[i+1]+=z.a[i]/NN,z.a[i]%=NN; //取mo慢，放到外面取
while(z.len>1&&!z.a[z.len])z.len--;
return z;
}
H ksm(H a,int n) //快速幂
{
if(n==1)return a;
H c=ksm(a,n>>1);
c=chen(c,c);
if(n&1)c=chen(c,a);
return c;
}
bool Chu(H a) //本来这个函数名是骂出题人的，怕和谐，就改了
{
if(a.len*n-n+1>s.len)return 0;
if(bigD(s,ksm(a,n)))return 1;
return 0;
}
int main()
{
// freopen("calc.in","r",stdin);
// freopen("calc.out","w",stdout);
scanf("%d",&n);
init(s);
if(n==1)
{
outit(s);
return 0;
}
H l,r,mid,ans;
in(l,1);
r=s;
while(bigD(r,l))
{
mid=jia(l,r);
mid=chu(mid);
if(Chu(mid))
{
if(bigD(mid,ans))ans=mid;
H c;
in(c,1);
l=jia(mid,c);
}
else r=rrr(mid);
}
outit(ans);
}