ZOJ(2562 More Divisors 求反素数经典应用!)

spoiler posted @ 2011年5月03日 04:15 in 数论 , 1638 阅读

题目大意:给一个N求不超过N的 哪个数的因子数最多,数目相同的取值小的那个!

题目分析:这里引进反素数知识:

反素数第一点:g(x)表示 x含有因子的数目,设 0<i<=x  则g(i)<=x;

反素数第二个特性:2^t1*3^t2^5^t3*7^t4..... 这里有 t1>=t2>=t3>=t4...

所以我们根据这两个属性 进行递归求解!

递归过程:

首先做出三条判断,第一是否该值不超过N的大小,第二比较因子的个数,更新最大的,即更新最大的反素数,第三如果因子数相等,则更新较小的。

然后枚举+递归不断尝试更新,使得得到因子数最大的那个!

代码+部分注释:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
long long bestres,bestsum,n;
long long pri[16]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47};
//res表示当前讨论的值,sum表示该值的因子数目,
//k表示讨论到第几个素数了,limit表示上次的幂的值
//这次幂的上限,就是体现t1>=t2>=t3...
void work(long long res, long long sum,int k,int limit ){
	if(res>n)//如果超过n就跳出!
		return ;
	if(sum>bestsum){
      //这次计算的因子数目比我以前过程的最大值还大,那么就要更新!
		bestres=res;
		bestsum=sum;
	}
	if(sum==bestsum&&res<bestres){
//如果因子数目一样,取值比较小的!
		bestres=res;
	}
	long long p=pri[k];
//记得第一次p=pri[k],因为下面i是从1开始计数的!
	for(int i=1;i<=limit;i++,p*=pri[k]){
		if(res*p>n)
			break;
		else
			work(res*p,sum*(i+1),k+1,i);
	}
}
int main(){
	while(scanf("%lld",&n)!=EOF){
		bestres=1LL;
		bestsum=1LL;
		work(1LL,1LL,0,50);
		printf("%lld\n",bestres);
	}
	return 0;
}

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter