最近想到要整理下以前学过的一些知识。首先先说说高精度压位储存的知识吧，具体实现是参照RXDoi神牛的，也是得到了他的不少帮助，这里表示感谢！
（需要模板的或者不想听废话的就直接翻到后面看我代码就行~）
首先，我们知道，高精度算法的最基本的思想是将Int、long long等类型储存不下的数按位存入数组中，这样逐位存可以让空间上没有问题。然而，问题来了，这样的时间效率显然是不够好的。
我们来看一道题：hdu1042。题目意思是计算n！，n<=10000。
我们来考虑一般的方法。首先可以大概估出n=10000时位数约为40000左右，我们可以开一个略大于这个值的数组来储存结果。然后计算过程（伪代码）如下：
For i=1 to n do
{
k=0;
For j=0 to 40000 do
{
t=a[j]*i+k;
k=t/10;
a[j]=t%10;
}
}
//即列竖式人脑算的过程，为了将高精度数（数组a）乘上i，则对于数组a每一位都应乘i.
//这里k是记录每一次乘上i后需要进位的数值，这样下一次加上k即为进位。
显然这种方法的时间复杂度应该是O（nm）{m为n！的最大位数} 于是会超时。
矛盾的关键就在于每次乘i都要对于每一位都要存，那么位数少一些不就行啦？
于是我们想到了一种压位储存的方法。记Base=10000，然后a数组的每一位都存的是不大于Base的数。其实意思就是Base进制（这里即万进制）。对于Base的取法一般10000或100000为宜。我这里取10000.那么这下a数组就不必开到40000了只需开到10000即可。
这样大大加快了效率，就能过了。（当然实际上可以做的更好，每次记录下当前的位数，就不用每次都循环到10000这么多）
下面详细介绍下我的写法。
主要准备介绍的基本操作有：高精度结构体的定义，读入，输出，加（减同理），乘，单精度除，乘方
整个高精度数我是写成一个结构体：
struct BigInt
{
int Len,s[MaxL];
//Len为高精度数的位数，s数组存每一位的数。（每一位都是小于Base的）
BigInt() {Len=1;memset(s,0,sizeof(s));}
//定义一个高精度数的时候的初始化
void clear() {while (Len>1&&s[Len-1]==0) Len--;}
//每次操作完毕的clear操作
void from_str(string c)
{
int L=c.length();Len=L/4+(L%4!=0);
for (int i=0;i<Len;i++)
for (int j=max(L-(i+1)*4,0);j<L-i*4;j++) s[i]=s[i]*10+c[j]-'0';
}
//转换string的数为高精度数
void get(int x)
{
Len+=2;
s[0]+=x;
for (int i=0;i<Len;i++) s[i+1]+=s[i]/Base,s[i]%=Base;
clear();
}
//转换int的数为高精度数（其实改写一下就是高精度数+单精度数的加法）
void read() {cin>>c;from_str(c);}
//读入一个数……
void print()
{
for (int i=Len-1;i>=0;i--)
{
if (i!=Len-1&&s[i]<1000) putchar('0');
if (i!=Len-1&&s[i]<100) putchar('0');
if (i!=Len-1&&s[i]<10) putchar('0');
printf("%d",s[i]);
}
puts("");
}
//输出，每一位如果缺0要补0.
};
然后是加、乘、单精度除、乘方（具体的直接贴代码了）
BigInt operator + (BigInt A,BigInt B)
{
A.Len=max(A.Len,B.Len);
for (int i=0;i<A.Len;i++) A.s[i]+=B.s[i];
for (int i=0;i<A.Len;i++) A.s[i+1]+=A.s[i]/Base,A.s[i]%=Base;
A.Len++;A.clear();return A;
}
BigInt operator * (BigInt A,BigInt B)
{
BigInt C;C.Len=A.Len+B.Len;
for (int i=0;i<A.Len;i++)
for (int j=0;j<B.Len;j++)
{
C.s[i+j]+=A.s[i]*B.s[j];
if (C.s[i+j]>top) C.s[i+j+1]+=C.s[i+j]/Base,C.s[i+j]%=Base;
}
for (int i=0;i<C.Len;i++) C.s[i+1]+=C.s[i]/Base,C.s[i]%=Base;
C.clear();return C;
}
BigInt operator / (BigInt A,int B)
{
for(int i=A.Len-1;i>=1;i--) A.s[i-1]+=(A.s[i]%B)*Base,A.s[i]/=B;
A.s[0]/=B;
A.clear();
return A;
}
BigInt Pow(BigInt a,int b)
{
BigInt res;res.from_str("1");
for (;b;b>>=1,a=a*a)
{
if (b&1) res=res*a;
if (b==1||!(res<=A)) return res;
}
return res;
}
提供一些模板题及我的代码：
Hdu1002 计算a+b，注意输出格式。
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int Base=10000,top=100000000;
string c;int n;
struct BigInt
{
int Len,s[3000];
BigInt() {Len=1;memset(s,0,sizeof(s));}
void clear() {while (Len>1&&s[Len-1]==0) Len--;}
void from_str(string c)
{
int L=c.length();Len=L/4+(L%4!=0);
for (int i=0;i<Len;i++)
for (int j=max(L-(i+1)*4,0);j<L-i*4;j++) s[i]=s[i]*10+c[j]-'0';
}
void read() {cin>>c;from_str(c);}
void print()
{
for (int i=Len-1;i>=0;i--)
{
if (i!=Len-1&&s[i]<1000) putchar('0');
if (i!=Len-1&&s[i]<100) putchar('0');
if (i!=Len-1&&s[i]<10) putchar('0');
printf("%d",s[i]);
}
}
};
BigInt operator + (BigInt A,BigInt B)
{
A.Len=max(A.Len,B.Len);
for (int i=0;i<A.Len;i++) A.s[i]+=B.s[i];
for (int i=0;i<A.Len;i++) A.s[i+1]+=A.s[i]/Base,A.s[i]%=Base;
A.Len++;A.clear();return A;
}
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
printf("Case %d:\n",i);
BigInt A,B;
A.read();B.read();
A.print();
printf(" + ");
B.print();
printf(" = ");
A=A+B;
A.print();
puts("");
if(i!=n) puts("");
}
return 0;
Hdu1042 计算n！。
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int Base=10000;
const int top=Base*Base;
const int MaxL=15000;
string c;int n;
struct BigInt
{
int Len,s[MaxL];
BigInt() {Len=1;memset(s,0,sizeof(s));}
void clear() {while (Len>1&&s[Len-1]==0) Len--;}
void from_str(string c)
{
int L=c.length();Len=L/4+(L%4!=0);
for (int i=0;i<Len;i++)
for (int j=max(L-(i+1)*4,0);j<L-i*4;j++) s[i]=s[i]*10+c[j]-'0';
}
void get(int x)
{
Len+=2;
s[0]+=x;
for (int i=0;i<Len;i++) s[i+1]+=s[i]/Base,s[i]%=Base;
clear();
}
void read() {cin>>c;from_str(c);}
void print()
{
for (int i=Len-1;i>=0;i--)
{
if (i!=Len-1&&s[i]<1000) putchar('0');
if (i!=Len-1&&s[i]<100) putchar('0');
if (i!=Len-1&&s[i]<10) putchar('0');
printf("%d",s[i]);
}
puts("");
}
};
BigInt operator * (BigInt A,BigInt B)
{
BigInt C;C.Len=A.Len+B.Len;
for (int i=0;i<A.Len;i++)
for (int j=0;j<B.Len;j++)
{
C.s[i+j]+=A.s[i]*B.s[j];
if (C.s[i+j]>top) C.s[i+j+1]+=C.s[i+j]/Base,C.s[i+j]%=Base;
}
for (int i=0;i<C.Len;i++) C.s[i+1]+=C.s[i]/Base,C.s[i]%=Base;
C.clear();return C;
}
int main()
{
while(scanf("%d",&n)==1)
{
BigInt A;
A.get(1);
for(int i=1;i<=n;i++)
{
BigInt B;
B.get(i);
A=A*B;
}
A.print();
}
return 0;
}
BZOJ1213 关于高精度开根，因为结果是整数，所以只需要二分答案然后判断就行了。
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int Base=10000,top=100000000;
string c;int n;
struct BigInt
{
int Len,s[3000];
BigInt() {Len=1;memset(s,0,sizeof(s));}
bool operator <= (const BigInt& B) const
{
if (Len!=B.Len) return Len<B.Len;
for (int i=Len-1;i>=0;i--) if (s[i]!=B.s[i]) return s[i]<B.s[i];
return 1;
}
void clear() {while (Len>1&&s[Len-1]==0) Len--;}
void from_str(string c)
{
int L=c.length();Len=L/4+(L%4!=0);
for (int i=0;i<Len;i++)
for (int j=max(L-(i+1)*4,0);j<L-i*4;j++) s[i]=s[i]*10+c[j]-'0';
}
void read() {cin>>c;from_str(c);}
void print()
{
for (int i=Len-1;i>=0;i--)
{
if (i!=Len-1&&s[i]<1000) putchar('0');
if (i!=Len-1&&s[i]<100) putchar('0');
if (i!=Len-1&&s[i]<10) putchar('0');
printf("%d",s[i]);
}
puts("");
}
} A,L,R,res,Mid;
BigInt operator + (BigInt A,BigInt B)
{
A.Len=max(A.Len,B.Len);
for (int i=0;i<A.Len;i++) A.s[i]+=B.s[i];
for (int i=0;i<A.Len;i++) A.s[i+1]+=A.s[i]/Base,A.s[i]%=Base;
A.Len++;A.clear();return A;
}
BigInt operator * (BigInt A,BigInt B)
{
BigInt C;C.Len=A.Len+B.Len;
for (int i=0;i<A.Len;i++)
for (int j=0;j<B.Len;j++)
{
C.s[i+j]+=A.s[i]*B.s[j];
if (C.s[i+j]>top) C.s[i+j+1]+=C.s[i+j]/Base,C.s[i+j]%=Base;
}
for (int i=0;i<C.Len;i++) C.s[i+1]+=C.s[i]/Base,C.s[i]%=Base;
C.clear();return C;
}
BigInt Pow(BigInt a,int b)
{
BigInt res;res.from_str("1");
for (;b;b>>=1,a=a*a)
{
if (b&1) res=res*a;
if (b==1||!(res<=A)) return res;
}
return res;
}
BigInt Shr(BigInt A)
{
for (int i=A.Len-1;i;i--) {A.s[i-1]+=(A.s[i]&1)*Base;A.s[i]>>=1;}
A.s[0]>>=1;A.clear();return A;
}
void Inc(BigInt &A)
{
A.s[0]++;for (int i=0;i<A.Len;i++) A.s[i+1]+=A.s[i]/Base,A.s[i]%=Base;
A.Len++;A.clear();
}
void Dec(BigInt &A)
{
A.s[0]--;for (int i=0;i<A.Len;i++) if (A.s[i]<0) A.s[i]+=Base,A.s[i+1]--;
A.clear();
}
int main()
{
scanf("%d",&n);
A.read();
L.from_str("0");
R.Len=(A.Len*4/n)/4+1;for (int i=0;i<R.Len;i++) R.s[i]=9999;
while (L<=R)
{
Mid=Shr(L+R);
if (Pow(Mid,n)<=A) res=Mid,L=Mid,Inc(L);else R=Mid,Dec(R);
}
res.print();
}
其中Shr，Inc，Dec分别是除二，加一，减一。
评论 (0)
