【算法】高精度模板

高精度加法

P1601 A+B Problem（高精）

#include<bits/stdc++.h>
using namespace std;

template<class T>inline void qmax(T &x,const T &y){if(x<y) x=y;}

int l1,l2,l;
string s1,s2;
int a[3][505];

void reverse(int x,int l){        //翻转
	for(int i=1;i<=l/2;i++) swap(a[x][i],a[x][l-i+1]);
}

void add(){
	for(int i=1;i<=max(l1,l2);i++){
		a[0][i]+=a[1][i]+a[2][i];
		if(a[0][i]>=10) a[0][i+1]+=a[0][i]/10,a[0][i]%=10,l=i+1;
	}
	qmax(l,max(l1,l2));
}

int main(){
	int i,j;
	cin>>s1>>s2;
	for(i=0;i<s1.size();i++) a[1][++l1]=s1[i]-'0';
	for(i=0;i<s2.size();i++) a[2][++l2]=s2[i]-'0';
	reverse(1,l1),reverse(2,l2);
	
	add();
	
	for(i=l;i>=1;i--) cout<<a[0][i];
	return 0;
}

高精度乘法

P1303 A*B Problem

#include<bits/stdc++.h>
using namespace std;

template<class T>inline void qmax(T &x,const T &y){if(x<y) x=y;}

int l1,l2,l;
string s1,s2;
int a[3][5005];

void reverse(int x,int l){        //·­×ª
	for(int i=1;i<=l/2;i++) swap(a[x][i],a[x][l-i+1]);
}

void Plus(){
	int i,j;
	for(i=1;i<=l1;i++) 
		for(j=1;j<=l2;j++) a[0][i+j-1]+=a[1][i]*a[2][j];
	
	l=l1+l2+1;
	for(i=1;i<=l;i++) 
		if(a[0][i]>=10) a[0][i+1]+=a[0][i]/10,a[0][i]%=10,qmax(l,i+1);
	for(i=l;i>=1;i--) 
		if(a[0][l]==0) l=i-1;
		else break;
}

int main(){
	int i,j;
	cin>>s1>>s2;
	for(i=0;i<s1.size();i++) a[1][++l1]=s1[i]-'0';
	for(i=0;i<s2.size();i++) a[2][++l2]=s2[i]-'0';
	reverse(1,l1),reverse(2,l2);
	
	Plus();
	if(l==0) cout<<0;
	else for(i=l;i>=1;i--) cout<<a[0][i];
	return 0;
}

高精度除法

P1480 A/B Problem

#include<bits/stdc++.h>
using namespace std;

template<class T>inline void qmax(T &x,const T &y){if(x<y) x=y;}

int l1,l;
long long x;
string s1;
long long a[5005];

void reverse(int l){        //翻转
	for(int i=1;i<=l/2;i++) swap(a[i],a[l-i+1]);
}

void Div(){
	for(int i=l1;i>=1;i--)
		a[i-1]+=(a[i]-(a[i]/x)*x)*10,a[i]/=x;
}

int main(){
	int i,j;
	cin>>s1>>x;
	for(i=0;i<s1.size();i++) a[++l1]=s1[i]-'0';
	reverse(l1);
	
	Div();
	
	for(i=l1;i>=1;i--)
		if(a[i]!=0) break;
	if(i<1) cout<<0;
	else for(l1=i;i>=1;i--) cout<<a[i]; 
	return 0;
}