记录编号	44810	评测结果	AAAAAAAAAA
题目名称	最多因子数	最终得分	100
用户昵称	Truth.Cirno	是否通过	通过
代码语言	C++	运行时间	0.085 s
提交时间	2012-10-20 11:31:06	内存使用	3.16 MiB

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;

/*treat "sunum" and "su[]" as "const int" ; after the assignment , at most ( when b==1,000,000,000 ) , sunum==3401 , su[0]==2 , su[3401] is empty */
int a,b,sqrtb,sunum=1,su[3500]={2}/*,rec[3500]*/,maxyinnum,whichnum;//su[3401]={2}

//use this to pruduce "su[]"
bool check(int num)
{
    int i,temp;
	if (num==1)
		return(0);
    temp=sqrt(num*1.0);
    for (i=0;i<sunum&&su[i]<=temp;i++)
        if (num%su[i]==0)
            return(0);
    return(1);
}

void dfs(int supos,int num,int yinnum)
{
//	//the solution is illegal
//	if (num>b)
//		return;
    
    //there is a better solution
    if (num>=a)
	{
        if (maxyinnum<yinnum)
        {
            maxyinnum=yinnum;
            whichnum=num;
        }
		else if (maxyinnum==yinnum&&whichnum>num)
		{
			whichnum=num;
		}
	}
	
    //no legal solutions ( not very important )
    int i,l,r,temp,temp2;
    l=(a-1)/num;
    r=b/num;
    if (l==r)
        return;
    
    ///////////////////////////////////////////////////////////////////////////////////////////
    ///////////////////////////////////////////////////////////////////////////////////////////
    ////Extra1 ( Attention!!!!!!! ) : deal with the nums with a "su[]" bigger than su[3400]////
    ///////////////////////////////////////////////////////////////////////////////////////////
    ///////////////////////////////////////////////////////////////////////////////////////////
    if (num<sqrtb)/* error : "<" was writtten as "<=" */
    {
        for (i=l+1;i<=r;i++)
		{
            if (check(i))
            {
				temp=(yinnum<<1);
				temp2=num*i;
                if (maxyinnum<temp)
                {
                    maxyinnum=temp;
                    whichnum=temp2;
                }
				else if (maxyinnum==temp&&whichnum>temp2)
				{
					whichnum=temp2;
				}
                break;
            }
		}
    }
    
//  //next solution will be illegal ( deleted , since it can be replaced by Extra 2 )
//  if (su[supos]>b||supos>=sunum)
//      return;
	
    //shortcut (when there is no better solutions)
    if (maxyinnum*1.0>yinnum*pow(2.0,log(b*1.0/num)/log(su[supos]*1.0)))
        return;
    
    //////////////////////////////////////////////
    //Extra2 ( Attention! ) : no legal solutions//
    //////////////////////////////////////////////
    if (num*su[supos]>b||supos>=sunum)
        return;
    
    //produce new solutions
    int muler;
    for (i=2,muler=su[supos];;i++,muler*=su[supos])
    {
		/* 1 and 2 may be dupped , but isn't , why ? In fact , I don't know . */
		if (muler>r)/*1*/
			break;
        dfs(supos+1,num*muler,yinnum*i);
		if (muler*1.0>r*1.0/su[supos])/*2*/
            break;
		/* 1 and 2 may be dupped , but isn't , why ? In fact , I don't know . */
    }
	dfs(supos+1,num,yinnum);
}

int main(void)
{
    freopen("divisors.in","r",stdin);
    freopen("divisors.out","w",stdout);
    
    cin>>a>>b;
    
    /*assignment*/
    int i;
    sqrtb=sqrt(b*1.0);//don't have to used the maxnum 1,000,000,000
    for (i=3;i<=sqrtb;i++)
	{
        if (check(i))
        {
            su[sunum]=i;
            sunum++;
        }
	}
    /*assignment*/
	
    if (b==1)
    {
        cout<<"Between 1 and 1,1 has a maximum of 1 divisors."<<endl;
        return(0);
    }
    
//  maxyinnum=2;
//  whichnum=a;
    dfs(0,1,1);
    
    //Eg : Between 1000 and 2000,1680 has a maximum of 40 divisors.
    cout<<"Between "<<a<<" and "<<b<<","<<whichnum<<" has a maximum of "<<maxyinnum<<" divisors."<<endl;
    
    return(0);
}