Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

谁帮我看看 我这个代码为什么会WA 知道的数据都测了 拜托那位大牛帮忙看一下 非常谢谢

Posted by xuyemin520 at 2011-05-06 19:35:10 on Problem 3101
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;

int pri[120000],num1[32000],num2[32000],cnt;
int fz[3001],fm[3001],gn[3001];
int sim[3001],tt[3001];

bool flag[120000];

int cmp(int a,int b){
	return a>b;
}

void get_pri(){
	int i,j;
	pri[1]=2;
	cnt=1;
	memset(flag,true,sizeof(flag));
	for(i=4;i<=120000;i+=2)
		flag[i]=false;
	for(i=3;i<=4000;i+=2)
		for(j=i*i;j<=120000;j+=2*i)
			flag[j]=false;
	for(i=3;i<=120000;i+=2)
		if(flag[i])
			pri[++cnt]=i;
	return ;
}
int gcd(int a,int b){
	int c;
	if(a<b){
		c=a;	a=b;
		b=c;
	}
	while(b){
		c=b;
		b=a%b;
		a=c;
	}
	return a;
}
int solve(){
	int cas,n,t,i,j,s;
	int maxn=0;
	long long ans,count;
	cin>>cas;
	for(i=1;i<=cas;i++)
		scanf("%d",&tt[i]);
	sort(tt+1,tt+1+cas,cmp);
	j=1;
	sim[1]=tt[1];
	for(i=1;i<=cas;i++)
		while(sim[j]!=tt[i])
			sim[++j]=tt[i];
	cas=j;
	if(cas==1){
		printf("1 1\n");
		return 0;
	}
	for(i=1;i<cas;i++){
		fz[i]=sim[i]*sim[cas];
		fm[i]=(sim[i]-sim[cas])*2;
		int mm=gcd(fz[i],fm[i]);
		fz[i]/=mm;
		fm[i]/=mm;
	}
	cas--;
	if(cas==1){
		printf("%d %d\n",fz[1],fm[1]);
		return 0;
	}
	maxn=sim[1];
	memset(num1,0,sizeof(num1));
	memset(num2,-1,sizeof(num2));
	for(i=1;i<=cas;i++){
		n=fz[i];
		for(j=1;j<=cnt&&pri[j]<=n;j++){
			s=0;
			while(n%pri[j]==0){
				s++;
				n/=pri[j];
			}
			if(num1[j]<s)
				num1[j]=s;
		}
	}
	for(i=1;i<=cas;i++){
		n=fm[i];
		for(j=1;j<=cnt&&pri[j]<=maxn;j++){
			s=0;
			while(n%pri[j]==0){
				s++;
				n/=pri[j];
			}
			if(num2[j]>s||num2[j]<0)
				num2[j]=s;
		}
	}
	for(i=1;i<=cnt&&pri[i]<=maxn;i++){
		if(num1[i]&&num2[i]&&num2[i]!=-1){
			if(num1[i]>=num2[i]){
				num1[i]-=num2[i];
				num2[i]=0;	
			}
			else{
				num2[i]-=num1[i];
				num1[i]=0;
			}
		}
	}
	ans=1;
	for(i=1;i<=cnt&&pri[i]<=maxn;i++){
		if(num1[i])
			ans*=(int)pow(((double)pri[i]),num1[i]);
	}
	count=1;
	for(i=1;i<=cnt&&pri[i]<=maxn;i++){
		if(num2[i]&&num2[i]!=-1)
			count*=(int)pow(((double)pri[i]),num2[i]);
	}
	printf("%lld %lld\n",ans,count);
	return 0;
}
int main(){
	get_pri();
	solve();
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator