| ||||||||||
| 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