题目大意

给出一个n，求小于等于n中“约数个数”最多的数与个数（n<=1e18）

约数个数与一般不同，举例说明：12 的约数有1  2  3  4  6  12，这些数分别有1  2  2  3  4  6 个约数，那12 有18 个约数的约数。

因为n的范围很大，所以不可以使用朴素做法。

我们这样思考：既然是求约数个数多且这个数尽量小，假如2^2*3^3和2^3*3^2都在n范围内，我们肯定是选择前者更优，因为两者约数个数是一样多的，均是（2+1）*（3+1），而前者更小。

可得到质因子的指数是单调不降的

注意！这里可能有个思想误区：既然选更小的质因子更优，为什么不全部由2累乘呢？

比如8和12，8=2^3,12=2^2*3，显然我们选12要更优，因为我们在判断更优情况的时候是已经保证了约数个数相同，而去选择更小的数，而不能一味往小选。（要注意前提条件，思想严谨性）。

再考虑“约数个数”

还是解释一下：比如12，可分解为2^2*3，那么质因子2的指数可以为0，1，2，质因子3的指数可以为0，1，两者的选择个数任意组合相乘就是最后的“约数个数”

具体实现，我们可以用dfs，因为我们发现用质因子去累乘，使用的质因子最多也是在几十的范围，就可以一个个枚举，而最后的答案在dfs时候就可以统计了

#include<bits/stdc++.h>
#define N 10000003
#define LL long long
#define INF 2100000000
using namespace std;
LL read()
{
    LL x=0,f=1;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
    while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
    return x*f;
}
LL n,tot=0;
LL ans=INF;
LL prime[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,51,53,57,59,61,67,71,73,79,83};
void dfs(LL num,LL pos,LL n,LL sum)
{
    if(sum>n)return ;
    if(num>tot){ans=sum,tot=num;}
    else if(tot==num&&ans>sum)ans=sum;
    for(int i=1;i<=100;++i)
    {
        LL res=pow(prime[pos],i);
        if(sum>n/res)break;
        dfs(num*((i+2)*(i+1)/2),pos+1,n,sum*res);
    }
}
int main()
{
//    freopen("b.in","r",stdin);
//    freopen("b.out","w",stdout);
    n=read();
    dfs(1,0,n,1);
    printf("%lld\n%lld",ans,tot);
} 
/*
*/

View Code

我在打的时候并没有在循环中从上一个prime的个数开始（因为dfs中ans和tot的更新方式可以保证ans是最小的了），如果要从上一个prime的个数开始，再存一个变量last就好了。

感觉这道题的思想还是很重要的，特别是推出质因子指数单调不降的那里，是解题的关键点，如果没有想到这个，朴素地枚举所有质因子的话，显然是过不了的。