题解 | #[NOIP2012]国王的游戏#

首先来看怎么确定高精度的位数，最多有1000各大臣，每个大臣左手数字最大为10000，所以相乘的最差结果就是10^4000，也就是至多是一个4000位的数（大臣手中数字不包括10000）。然后就是基本的高精度乘法和高精度除低精度的除法。

#include<bits/stdc++.h>
using namespace std;
int n;
const int M=4005;	//M为高精度位数 
struct node{
	int a,b,sum;
	bool operator<(const node& p)const{
		return sum<p.sum;
	}
}a[M];
int g[M];
int len=1;
void mul(int x){
	for(int i=1;i<=len;i++)	g[i]*=a[x].a;
	for(int i=1;i<=len;i++){
		g[i+1]+=g[i]/10;
		g[i]=g[i]%10;
	}
	len++;	//进位后g的长度加一，4000*2这种没进位的也不用担心，去掉前导0的操作会解决
	while(g[len]>9){
		g[len+1]+=g[len]/10;
		g[len]=g[len]%10;
		len++;
	}
	if(g[len]==0)	len--;//去掉前导0，前导0只可能有一个，就是类似4000*2这样的情况，虽然len增加，但是没进位
	
}
void div(){
	for(int i=len;i>=1;i--){
		g[i-1]+=((g[i]%a[n].b)*10);
		g[i]=g[i]/a[n].b;
	}
	while(g[len]==0) len--;		//除法运算可能有多个前导0产生  
    if(len==0)    cout<<1;        //重要，是向下取整为0的情况
} 
int main(){
	cin>>n;
	cin>>a[0].a>>a[0].b;
	for(int i=1;i<=n;i++){
		cin>>a[i].a>>a[i].b;
		a[i].sum=a[i].a*a[i].b;
	}	
	sort(a+1,a+1+n);
	g[1]=a[0].a;
	for(int i=1;i<n;i++) mul(i);
	div();	//高精度除法 
//	cout<<len<<endl;
	for(int i=len;i>=1;i--) cout<<g[i];
	return 0;
	
}

高精度乘法单列出来

void mul(int x){
	for(int i=1;i<=len;i++)	g[i]*=a[x].a;
	for(int i=1;i<=len;i++){
		g[i+1]+=g[i]/10;
		g[i]=g[i]%10;
	}
	len++;	//进位后g的长度加一，4000*2这种没进位的也不用担心，去掉前导0的操作会解决
	while(g[len]>9){
		g[len+1]+=g[len]/10;
		g[len]=g[len]%10;
		len++;
	}
	if(g[len]==0)	len--;//去掉前导0，前导0只可能有一个，就是类似4000*2这样的情况，虽然len增加，但是没进位
	
}

高精度除低精度除法单列出来,注意向下取整为0的情况，如果不特判，那么len被减没后，就输出不出来任何数。

void div(){
	for(int i=len;i>=1;i--){
		g[i-1]+=((g[i]%a[n].b)*10);
		g[i]=g[i]/a[n].b;
	}
	while(g[len]==0) len--;		//除法运算可能有多个前导0产生  
    if(len==0)    cout<<1;        //重要，是向下取整为0的情况
}