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 jsjhoubo at 2007-11-29 23:14:28 on Problem 3471
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>

__int64 coffi[120],f1[120],f2[120],a0;
__int64 ans[120];
__int64 fact[200000];

int count,n,t,fnum;
int cmp(const void *a,const void *b)
{
	__int64 a1=(*(__int64*)a);
	__int64 b1=(*(__int64*)b);
	if(a1>b1)
		return 1;
	if(a1<b1)
		return -1;
	return 0;
}

void div(__int64 num)
{
	__int64 r[2]={1,num};
	int i;
	while(t>=1)
	{
		for(i=1;i<=t;i++)
		{
			f2[i-1]=f1[i-1]/r[0];
			f1[i]=f1[i]-f2[i-1]*r[1];
		}
		if(f1[t]!=0)
			break;
		for(i=0;i<t;i++)
			f1[i]=f2[i];
		ans[count++]=-num;	
		t--;
	}
}

int main()
{
	int i,tt,j;
	__int64 aa,ii;
//	freopen("1.in","r",stdin);
	while(scanf("%d",&n)!=EOF)
	{
		coffi[0]=1;
		count=0;
		for(i=1;i<=n;i++)
			scanf("%I64d",coffi+i);		
		i=n;
		while(!coffi[i])
		{
			i--;
			ans[count++]=0;
		}
		if(i==0)
		{
			goto l1;
		}
		n=i;
		a0=coffi[n];
		if(a0<0)
		{
			a0=-a0;
			for(i=0;i<=n;i++)
				coffi[i]=-coffi[i];
		}
		tt=(int)sqrt((double)a0);		
		for(ii=1,i=1,j=0;i<=tt+1;i++,ii++)
		{
			if(a0%i==0)
			{
				aa=a0/ii;
				if(aa!=ii)
				{
					fact[j++]=ii;
					fact[j++]=aa;
				}
				else 
					fact[j++]=ii;
			}
		}
		fnum=j;	
		qsort(fact,fnum,sizeof(fact[0]),cmp);
		for(i=1,j=1;i<fnum;i++)
		{
			if(fact[i]==fact[i-1])
				continue;
			fact[j++]=fact[i];
		}
		fnum=j;
		for(i=0;i<fnum;i++)
		{
			for(j=0;j<=n;j++)
				f1[j]=coffi[j];
			t=n;
			div(fact[i]);
			for(j=0;j<=n;j++)
				f1[j]=coffi[j];
			t=n;
			div(-fact[i]);
		}
		qsort(ans,count,sizeof(ans[0]),cmp);
l1:	
		printf("%d\n",count);
		for(i=0;i<count;i++)
			printf("%I64d\n",ans[i]);
	}
	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