高精度Operator用法及压位

orz hhw posted @ 2015年5月16日 09:51 in 算法学习 with tags 模板 高精度 bzoj , 2923 阅读

看到一道BZOJ1089,有高精度各种操作,可以当高精度模板了

#include<cstdio>
#define rad 10000//压位 
using namespace std;
int n,d,i,now;
struct data{int v[2005],l;}f[30];//v为值,l为长度 
void print(data a){printf("%d",a.v[a.l]);for(i=a.l-1;i;i--)printf("%04d",a.v[i]);}
data operator*(data a,data b){//高精度乘法 
	data c;
	for(int i=1;i<=a.l+b.l;i++)c.v[i]=0;
	for(int i=1;i<=a.l;i++)
		for(int j=1;j<=b.l;j++)
			c.v[i+j-1]+=a.v[i]*b.v[j];
	c.l=a.l+b.l-1;
	for(int i=1;i<=c.l;i++){
		c.v[i+1]+=c.v[i]/rad;
		c.v[i]%=rad;
	}
	if(c.v[c.l+1])c.l++;
	return c;
}
data operator^(data a,int p){//高精度求快速幂 
	data c;
	c.l=1;c.v[1]=1;
	for(;p;p>>=1,a=a*a)if(p&1)c=c*a;
	return c;
}
data operator-(data a,data b){//高精度减高精度 
	for(int i=1;i<=a.l;i++){
		a.v[i]-=b.v[i];
		if(a.v[i]<0){
			a.v[i]+=rad;
			a.v[i+1]--;
		}
	}
	while(a.l>1&&!a.v[a.l])a.l--;
	return a;
}
data operator+(data a,int p){//高精度加单精度 
	a.v[1]+=p;
	int now=1;
	while(a.v[now]>=rad){
		a.v[now+1]+=a.v[now]/rad;
		a.v[now]%=rad;
		now++;
	}
	if(now>a.l)a.l=now;
	return a;
}
int main(){
	scanf("%d%d",&n,&d);
	if(!d){puts("1");return 0;}
	f[0].l=f[0].v[1]=1;
	for(i=1;i<=d;i++)f[i]=(f[i-1]^n)+1;
	print(f[d]-f[d-1]);
}
Avatar_small
hhw 说:
2015年5月16日 14:09

然而你这个高精度连负数都不兹磁

Avatar_small
hhw 说:
2015年5月16日 14:11

而且还不兹磁高精度加高精度和高精度除法,而且高精度乘法还是暴力实现的。。。

Avatar_small
orz hhw 说:
2015年5月16日 18:24

胡主力您是很强嘛