Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
谁帮我看看 我这个代码为什么会WA 知道的数据都测了 拜托那位大牛帮忙看一下 非常谢谢#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator