divi.cpp

正整数x 的约数是能整除x 的正整数。正整数x 的约数个数记为div(x)。例如

#include <stdio.h>
#include <memory.h>
#include <math.h>
#define Maxint 31623
int  prime[Maxint+1];
int  n_prime,best;

int calc_prime(int n)   //用筛法求出在n范围内的素数列表
{
	int i,j;
	bool isprime[Maxint+1];
	memset(isprime,0,sizeof(isprime));
	if(n>Maxint) n=Maxint;
	for(i=2; i*i<=n; i++)
	{
		if(!isprime[i])
			for(j=i+i; j<=n; j+=i)
				isprime[j]=1;

	}
	j=0;
	for(i=2; i<=n; i++)
		if(isprime[i]==0)
			prime[j++]=i;
	return j;
}

//枚举质数,在给定的数据范围内搜索构成一个number,满足div(number)最大
void find(int total, int down, int up, int number, int start) 
//total当前的约束个数，down、up上下界，number由当前这total个约束构成的值，start起始的素数
{
	if(number>=1 && total>best)
		best=total;
	if(down==up && down>number)
		if(total*2>best) best=total*2;
	for(int i=start; i<n_prime; i++)
	{
		if(prime[i]>up) return ; 
		else {
			int k=prime[i],t=total,low=down-1,high=up,num=number;
			while(true) {
				t+=total;
				low/=k;
				high/=k;
				if(low==high) break;  //在当前数据范围内，f所能达到的最大的
				num*=k;
				find(t,low+1,high,num,i+1);
			}
			//t*logk(up)<best 假设当前上界最多可以被分解为k的个数为p，
			//而p个若都是不同素数的话,构成的个数为p=2^p最大,
			//根据乘法原理，那么t*p<test说明继续往下做没有意义，可以剪枝
			int p=int(log(up)/log(k)); 
			p=1<<p;
			if(total*p<best) return;
		}
	}
}

void swap(int &a, int &b)
{
	int temp;
	temp=a;
	a=b;
	b=temp;
}

int main()
{
	int s,f;
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	scanf("%d%d",&s,&f);
	if(s>f) swap(s,f);
	n_prime=calc_prime(f);
	if(s==1&&f==1) 
		best=1;
	else
	{
		best=2;
		find(1,s,f,1,0);
	}
	printf("%d\n",best);

	return 0;
}