首页 > 代码库 > ZOJ 1133

ZOJ 1133

2024-07-18 02:01:11   220人阅读

Smith数的定义是各位数字之和与它的各个质因数（可以重复）的各位数字之和的总和相同的数，且不是素数。

题目本身是一道水题，数据尤其水。

下面的代码中加了一个优化：

先将所有询问按询问的数字升序排序，处理某个询问A时，如果结果是B，那么对其后询问值小于B的所有询问，都直接

给出答案为B。

例如：

23

24

25

26

27

0

在处理23时得到58，由于后面四个数都小于58，于是后面四个询问直接得到答案58而不必重复劳动。

最后再将所有询问按原先次序排序即可。

这样总体的平均时间复杂度介于O(m)和O(mlogm)之间，m为询问个数。

以下为代码。

时间：10毫秒

#include "stdio.h"#include "string.h"#include "stdlib.h"#include "math.h"int prime[1200];int Smith[5];struct query{	int ask,pos,ans;};int cmp_by_ask(const void *a,const void *b){	return (*(query *)a).ask-(*(query *)b).ask;}int cmp_by_pos(const void *a,const void *b){	return (*(query *)a).pos-(*(query *)b).pos;}void getPrime(){	memset(prime,0,sizeof(prime));	int i,j,sq,flag;	prime[1]=2;	prime[2]=3;	prime[3]=5;	prime[4]=7;	prime[0]=4;	for(i=11;i<=10100;i++){		if(!(i%2&&i%3&&i%5&&i%7))continue;		sq=(int)(ceil(sqrt((double)i))+1);		flag=1;		for(j=11;j<=sq;j++){			if(i%j==0){				flag=0;				break;			}		}		if(flag){			prime[0]++;			prime[prime[0]]=i;		}	}}int getSum(int x){	int sum=0;	while(x){		sum+=(x%10);		x/=10;	}	return sum;}int is_Smith(int x){	int sum1=0,sum2=getSum(x),i,j,cnt=0;	for(i=1;i<=prime[0];i++){		while(x%prime[i]==0){			sum1+=getSum(prime[i]);			cnt++;			x/=prime[i];		}	}	if(x!=1){		sum1+=getSum(x);		cnt++;	}	if((sum1==sum2)&&(cnt>1))return 1;	else return 0;}int main(){	query p[50000];	int i,j,n,k,top;	top=0;	while(1){		scanf("%d",&p[top].ask);		if(p[top].ask==0)break;		p[top].pos=top;		p[top].ans=-1;		top++;	}	qsort(p,top,sizeof(p[0]),cmp_by_ask);	getPrime();	//for(i=0;i<top;i++){		//printf("%d ",p[i].ask);	//}//	//printf("\n");	for(i=0;i<top;i++){		//printf("I=%d.\n",i);		j=p[i].ask+1;		while(1){			if(is_Smith(j)){				p[i].ans=j;				break;			}			else j++;		}		//printf("j=%d.\n",j);		for(k=i+1;k<top;k++){			//printf("k=%d.\n",k);			if(p[k].ask<j){				p[k].ans=j;			}			else break;		}		//printf("***k=%d.\n",k);		i=k-1;	}	qsort(p,top,sizeof(p[0]),cmp_by_pos);	for(i=0;i<top;i++){		printf("%d\n",p[i].ans);	}	return 0;}

 


联系
我们