记录编号	59380	评测结果	AAAAAAAAAA
题目名称	[NOI 2006]神奇口袋	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.242 s
提交时间	2013-05-05 19:53:29	内存使用	0.63 MiB

#include<iostream>
#include<cstdio>
#include<cmath>
#include<deque>
#include<algorithm>
using namespace std;
const int SIZEN=1010;
int a[SIZEN]={0};
int y[SIZEN]={0};//颜色序列
int t,n,d;//这里的t,n和原题中是反着的
//(论变量命名规则统一的重要性)
int sum=0;//小球总数
void read(void){
	scanf("%d%d%d",&n,&t,&d);
	int i,temp,c;
	for(i=1;i<=n;i++) scanf("%d",&a[i]),sum+=a[i];
	for(i=1;i<=t;i++) scanf("%d%d",&temp,&c),y[i]=c;
}
const int SIZEP=20010;
int p[SIZEP]={0};
int psum;
void prime(void){//筛法生成素数
	bool l[SIZEP]={0};
	int i,j,k=1,temp;
	temp=(int)sqrt((double)SIZEP);
	for(i=2;i<SIZEP;i++){
		if(!l[i]){//素数
			p[k]=i,k++;
			if(i<=temp){
				for(j=i*i;j<=SIZEP;j+=i) l[j]=1;
			}
		}
	}
	psum=k-1;
}
int expz[SIZEP]={0},expm[SIZEP]={0};//分子分母的标准分解式
void decom(int x,int s[SIZEP]){//将x分解,叠加于s中
	int i;
	for(i=1;x>1&&i<=psum;i++){
		while(x%p[i]==0){
			s[i]++;
			x/=p[i];
		}
	}
}
void getseq(void){
	int i;
	for(i=1;i<=t;i++){
		decom(a[y[i]],expz);
		decom(sum,expm);
		a[y[i]]+=d,sum+=d;
	}
}
void reduct(void){
	int i,temp;
	for(i=1;i<=psum;i++){
		temp=min(expz[i],expm[i]);
		expz[i]-=temp,expm[i]-=temp;
	}
}
const int SIZEL=10001;
class HP{
public:
	int s[SIZEL];//数
	int l;//长度,不是指针
	void clear(void){
		int i;
		for(i=0;i<SIZEL;i++) s[i]=0;
		l=0;
	}
	HP(){clear();}
	void outint(void){
		int i;
		for(i=l-1;i>=0;i--) cout<<s[i];
	}
};
HP operator * (HP a,int b){//a*b
	int i;
	for(i=0;i<a.l;i++) a.s[i]*=b;
	for(i=0;i<a.l||a.s[i]!=0;i++){
		a.s[i+1]+=a.s[i]/10;
		a.s[i]%=10;
	}
	a.l=a.l>i?a.l:i;
	while(!a.s[a.l-1]) a.l--;
	return a;
}
HP fz,fm;
void calc(void){
	fz.l=1,fz.s[0]=1;
	fm.l=1,fm.s[0]=1;
	int i,j;
	for(i=1;i<=psum;i++){
		for(j=1;j<=expz[i];j++){
			fz=fz*p[i];
		}
	}
	for(i=1;i<=psum;i++){
		for(j=1;j<=expm[i];j++){
			fm=fm*p[i];
		}
	}
}
void write(void){
	fz.outint();
	printf("/");
	fm.outint();
}
int main(){
	freopen("bag.in","r",stdin);
	freopen("bag.out","w",stdout);
	read();
	prime();
	getseq();
	reduct();
	calc();
	write();
	return 0;
}