记录编号	96101	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[NEERC2004][POJ2013]头奖	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	2.205 s
提交时间	2014-04-10 21:45:00	内存使用	0.32 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<iomanip>
#include<cmath>
using namespace std;
typedef long long ll;
const int SIZEL=100,SIZEP=10010,MAXP=100010,SIZEN=20;
const ll BASE=1e8;
class HPINT{
public:
	ll s[SIZEL];
	int len;//从0开始
	void clear(void){//零
		memset(s,0,sizeof(s));
		len=1;
	}
	void print(void){
		cout<<s[len-1];
		for(int i=len-2;i>=0;i--){
			cout<<setfill('0')<<setw(8)<<s[i];
		}
		cout<<endl;
	}
	void opposite(void){//所有位上乘-1
		for(int i=0;i<len;i++) s[i]*=-1;
	}
	void operator *= (ll b){
		int i;
		for(i=0;i<len;i++) s[i]*=b;
		for(i=0;i<len||s[i];i++){
			s[i+1]+=s[i]/BASE;
			s[i]%=BASE;
		}
		if(i>len) len=i;
		while(len>1&&!s[len-1]) len--;
	}
	bool div(ll b){//若被b整除就除
		ll s1[SIZEL];
		memcpy(s1,s,sizeof(s1));
		int i,r;
		for(i=len-1;i>=0;i--){
			if(i) s1[i-1]+=(s1[i]%b)*BASE;
			else if(s1[i]%b){return false;}
			s1[i]/=b;
		}
		memcpy(s,s1,sizeof(s1));
		while(len>1&&!s[len-1]) len--;
		return true;
	}
	void operator +=(HPINT &b){
		len=max(len,b.len);
		int i;
		for(i=0;i<len;i++) s[i]+=b.s[i];
		for(i=0;i<len||s[i];i++){
			while(s[i]<0) s[i]+=BASE,s[i+1]--;
			s[i+1]+=s[i]/BASE;
			s[i]%=BASE;
		}
		if(i>len) len=i;
		while(len>1&&!s[len-1]) len--;
	}
};
vector<ll> allprime;
void getprime(int n){
	bool flag[MAXP]={0};
	int i,j,temp;
	temp=sqrt(n+0.0);
	for(i=2;i<=n;i++){
		if(!flag[i]){
			allprime.push_back(i);
			if(i<=temp){
				for(j=i*i;j<=n;j+=i) flag[j]=true;
			}
		}
	}
}
vector<ll> prime;
int factnum[SIZEN][SIZEL]={0};
int luckylcm[SIZEL]={0};
int N;
ll lucky[SIZEN]={0};
HPINT numer,denom;
void simplify(void){
	for(int i=0;i<prime.size();i++){
		while(luckylcm[i]&&numer.div(prime[i])) luckylcm[i]--;
	}
	denom.clear();denom.s[0]=1;
	for(int i=0;i<prime.size();i++) for(int j=1;j<=luckylcm[i];j++) denom*=prime[i];
}
void test(int code){
	int fn[SIZEL]={0},tot=0;
	for(int i=0;i<N;i++){
		if((code>>i)&1){
			tot++;
			for(int j=0;j<prime.size();j++) fn[j]=max(fn[j],factnum[i+1][j]);
		}
	}
	//现在fn里存的是这一坨数的lcm
	for(int i=0;i<prime.size();i++) fn[i]=luckylcm[i]-fn[i];
	HPINT temp;
	temp.clear();temp.s[0]=1;
	for(int i=0;i<prime.size();i++){
		for(int j=1;j<=fn[i];j++) temp*=prime[i];
	}
	if((tot&1)==0) temp.opposite();
	numer+=temp;
}
void work(void){
	for(int i=1;i<(1<<N);i++) test(i);
	simplify();
	numer.print();
	denom.print();
}
void getfact(void){
	bool exi[SIZEP]={0};
	for(int i=1;i<=N;i++){
		ll temp=lucky[i];
		for(int j=0;temp>1&&j<allprime.size();j++){
			while(temp%allprime[j]==0){
				if(!exi[j]){
					exi[j]=true;
					prime.push_back(allprime[j]);
				}
				temp/=allprime[j];
			}
		}
		if(temp!=1) prime.push_back(temp);
	}
	for(int i=1;i<=N;i++){
		ll temp=lucky[i];
		for(int j=0;temp>1&&j<prime.size();j++){
			while(temp%prime[j]==0){
				factnum[i][j]++;
				temp/=prime[j];
			}
		}
	}
	numer.clear();
	for(int j=0;j<prime.size();j++)	for(int i=1;i<=N;i++) luckylcm[j]=max(luckylcm[j],factnum[i][j]);
}
void read(void){
	scanf("%d",&N);
	for(int i=1;i<=N;i++) scanf("%lld",&lucky[i]);
}
int main(){
	freopen("jackpot.in","r",stdin);
	freopen("jackpot.out","w",stdout);
	getprime(1e5);
	read();
	getfact();
	work();
	return 0;
}