南邮 OJ 1203 最多约数问题

最多约数问题

时间限制(普通/Java) :  20000 MS/ 30000 MS          运行内存限制 : 81920 KByte

总提交 : 483            测试通过 : 61 

比赛描述

   正整数x的约数是能整除x的正整数。正整数x的约数个数记为div（x）。例如，1,2,5,10都是正整数10的约数，且div(10)=4。 对于给定的2个正整数a<=b，编程计算a与b之间约数个数最多的数。

输入

输入的第1行有两个正整数a和b。

输出

若找到的a和b之间约数个数最多的数是x，则输出div(x)。

样例输入

1 36

样例输出

9

题目来源

算法设计与实验题解

//设正整数x的质因子分解为 x=p1^N1*p2^N2...pn^Nn
//则div = (N1+1)(N2+1)...(Nn+1)

#include<stdio.h>
#define MAX_P 10000		//最大的质数
#define P_NUM 1229		//质数的个数

int prime[P_NUM+1];		//存放素数
int prime_num;			//素数的总个数
int max_num;			//最多约数的个数
int numb;				//有着最多约数的个数

void get_primes(){
	bool is_prime[MAX_P+1];
	int i,j;
	for(i=2;i<=MAX_P;++i){
		is_prime[i] = 1;
	}
	for(i=2;i<=MAX_P;++i){
		if(is_prime[i]){
			for(j=i<<1;j<=MAX_P;j+=i){
				is_prime[j] = 0;
			}
		}
	}
	for(i=2,j=0;i<=MAX_P;++i){
		if(is_prime[i]){
			prime[++j] = i;
		}
	}
	prime_num = j;
}
//from  :第几个质数
//total :当前约数最多个数
//number:为当前搜索到的数,total是指number中包含的因子数
//low   :区间下限
//up    :区间上限
void search(int from,int total,int number,int low,int up){
	if(number>=1){							//约数个数最多的数
		if ((total>max_num) || ((total==max_num) && (number<numb)) ){
			max_num = total;				//约数最多个数
			numb = number;					//约数最多的数，约数个数相同时，记录更大的数
		}
	}
	if((low==up) && (low>number)){			//区间中只有一个数，且大于当前约数最多的数
		search(from,total*2,number*low,1,1);// ?
	}
	for(int i=from; i<=prime_num; i++){		//对质数进行枚举
		if(prime[i]>up){					//质数大于上届，返回
			return;
		}else{
			int cur_prime=prime[i];			//当前素数
			int div_low=low-1;				//区间左端点-1
			int div_up=up;					//区间右端点
			int cur_num=number;				//当前约数最多的数
			int count=total;				//约数计数
			int m=1;
			while (true){
				m++;
				count += total;
				div_low /= cur_prime;
				div_up /= cur_prime;
				if(div_low == div_up){
					break;				//合法性剪枝,以当前状态搜索下去，结果肯定不在区间内了,可剪去
				}						//不过，这一剪枝作用不是很大，因为即使不剪，再搜索一层也就退出了
				cur_num *= cur_prime;
				search(i+1, count, cur_num, div_low+1, div_up);	//深度优先，搜索下一级？
			}
			m = 1<<m;
			if (total < max_num/m){		//当前所能取到的（理想情况）最大约数个数就是total*2^q。
				return;					//如果这个数仍然无法超过当前最优解，则这一分支不可能产生最优解，可以剪去
			}
		}
	}
}

int main(){
	get_primes();
	int a,b;
	scanf("%d%d",&a,&b);
	if(a==1 && b==1){
		return 1;
	}else{
		max_num=2;
		search(1,1,1,a,b);	//从第一个质数开始搜索，当前约数最多个数为1，当前约数最多的数为1
	}						//区间为[a,b]
	printf("%d\n",max_num);
}