南郵 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);
}