C++实现高精度大整数及其运算
目录
高精度大整数
对于一个数,如果其超过了0x7fffffff,则无法用int存储,如果超过2^63-1则long long也无法存储。因此构造结构体来存储这样的高精度大数。
头文件
#include<cstdio>
#include<cstring>
using namespace std;
结构体
struct bign{ //存123时: d={3,2,1}llen =3;
int d[1000];
int len;
bign(){
memset(d,0,sizeof(d));
len = 0;}
};
通过字符数组赋值
bign change(char str[]){ //通过字符串读取大整数
//str[]={'1','2','3'} ->a.b={3,2,1}
bign a;
a.len = strlen(str);
for(int i=0;i<a.len;i++){
a.d[i] = str[a.len-1-i] - '0';
}
return a;
}
输出大整数
void print(bign a){ //输出大整数
for(int i=a.len-1;i>=0;i--)
printf("%d",a.d[i]);
return;
}
大整数的比较
int compare(bign a,bign b){ //比较a和b的大小,a>b返回1,相等返回0,a<b返回-1
if(a.len>b.len) return 1;
if(a.len<b.len) return -1;
for(int i=a.len-1;i>=0;i--){
if(a.d[i]>b.d[i]) return 1;
if(a.d[i]<b.d[i]) return -1;
}
return 0;
}
大整数的运算
大整数之间的加法
bign add(bign a,bign b){ //大整数之间进行加法
bign c;
int carry = 0; //进位
for(int i=0;i<a.len||i<b.len;i++){
int temp = a.d[i]+b.d[i] + carry;
c.d[c.len++] = temp%10;
carry = temp/10;
}
if(carry!=0) c.d[c.len++] = carry;
return c;
}
大整数之间的减法
bign sub(bign a,bign b){ //大整数之间进行减法
bign c;
for(int i=0;i<a.len||i<b.len;i++){
if(a.d[i]<b.d[i]){ //低位不够减,需要借位
a.d[i+1]--;
a.d[i]+=10;
}
c.d[c.len++] = a.d[i]-b.d[i];
}
while(c.len-1>=1&&c.d[c.len-1]==0)
c.len--; //去除高位0
return c;
}
高精度大整数与低精度的乘法
bign multi(bign a,int b){ //高精度大整数与低精度的乘法
bign c;
int carry = 0; //进位
for(int i=0;i<a.len;i++){
int temp = a.d[i]*b + carry;
//printf("%d*%d+%d\n",a.d[i],b,carry);
c.d[c.len++] = temp%10;
carry = temp / 10;
}
while(carry!=0){
c.d[c.len++] = carry%10;
carry/=10;
}
return c;
}
高精度除以低精度数,同时返回r为余数
bign divide(bign a,int b,int& r){ //高精度除以低精度,r为余数
bign c;
c.len = a.len;
r=0;
for(int i=a.len-1;i>=0;i--){
r = r*10 + a.d[i];
if(r<b) c.d[i] = 0;
else{
c.d[i] = r/b;
r %= b;
}
}
while(c.len-1>=1&&c.d[c.len-1]==0){
c.len--;
}
return c;
}
其他运算
比如大整数与大整数的乘除略。。。。
使用示例
例题1(贪心+大整数)
题目
洛谷P1080 国王游戏
分析
此题需要先贪心找到排序规律为按照每个人的左右手乘积非降序排列,在计算最小值时累乘的过程中可能数字溢出，所以要使用大整数，但是根据题目描述大整数开100001位是不够的需要开的更大,但是实际测试数据并没有这么大。
AC代码
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 10001;
pair<int,int> nums[maxn]; //first 右手,second左手
struct bign{ //存123时: d={3,2,1}llen =3;
int d[maxn];
int len;
bign(){
memset(d,0,sizeof(d));
len = 0;}
}res,sum,ans; //res最终结果,sum累乘结果,ans比较变量
bign multi(bign a,int b){ //高精度大整数与低精度的乘法
bign c;
int carry = 0; //进位
for(int i=0;i<a.len;i++){
int temp = a.d[i]*b + carry;
//printf("%d*%d+%d\n",a.d[i],b,carry);
c.d[c.len++] = temp%10;
carry = temp / 10;
}
while(carry!=0){
c.d[c.len++] = carry%10;
carry/=10;
}
return c;
}
bign divide(bign a,int b,int& r){ //高精度除以低精度,r为余数
bign c;
c.len = a.len;
r=0;
for(int i=a.len-1;i>=0;i--){
r = r*10 + a.d[i];
if(r<b) c.d[i] = 0;
else{
c.d[i] = r/b;
r %= b;
}
}
while(c.len-1>=1&&c.d[c.len-1]==0){
c.len--;
}
return c;
}
int compare(bign a,bign b){ //比较a和b的大小,a>b返回1,相等返回0,a<b返回-1
if(a.len>b.len) return 1;
if(a.len<b.len) return -1;
for(int i=a.len-1;i>=0;i--){
if(a.d[i]>b.d[i]) return 1;
if(a.d[i]<b.d[i]) return -1;
}
return 0;
}
void print(bign a){ //输出大整数
for(int i=a.len-1;i>=0;i--)
printf("%d",a.d[i]);
return;
}
int cmp(pair<int,int> a,pair<int,int> b){
return a.first*a.second<b.first*b.second;
}
int main(){
int n;
scanf("%d",&n);
scanf("%d %d",&nums[0].first,&nums[0].second);
for(int i=1;i<=n;i++)
scanf("%d %d",&nums[i].first,&nums[i].second);
sort(nums+1,nums+1+n,cmp);
sum.d[0] = 1; sum.len = 1;
for(int i=1;i<=n;i++){
int r = 0; //存余数
sum = multi(sum,nums[i-1].first);
ans = divide(sum,nums[i].second,r);
if(compare(ans,res)==1)
res = ans;
}
print(res);
return 0;
}