题解 P1463 【[SDOI2005]反素数ant】

· · 题解

题目解释放在代码注释里面了~

欢迎吐槽与建议

/*
1.
一个数的约数个数=所有素因子的幂次+1的乘积
这个直观的理解就是 2^x*3^y 我能拆出来 
2^0*3^0
2^0*3^1
2^0*3^2
……
2^1*3^0
2^1*3^1
……
2^2*3^0
……
2^x*3^0
……
2^x*3^y
根据乘法原理 2一共有x+1个幂 3有y+1个幂 所以就是(x+1)*(y+1)

2.
写一个暴力跑程序会发现一个2000000000以内的数字不会有超过12个素因子

3.
较小的数的幂次一定大于等于较大的数的幂次

之后就是赤裸裸的DFS暴搜了 

*/

#include <cstdio>
#include <algorithm>

typedef long long ll;
ll n;
int ans=1,num=1;

ll Max,last;
//1的确不是质数 但是x^0需要用到 
int prime[15]={1,2,3,5,7,11,13,17,19,29,31};

//dep的意义是当前的第几个素数 Num是当前数字大小 tot是当前约数的和 limit是上一个素数的幂次对本次的限制约束
void dfs(int dep,ll Num,int tot,int limit){
    if(dep==12){
        //当前值大于记录值  并且约数也比上次那个多 
        if(Num > Max && tot> last){
            Max = Num;
            last = tot;
        }
        //当前值小于记录值  并且约数也比上次那个多  记录值不合法 
        /*这里这个“= ”特别说明一下
        g(x)>g(i) 0<i<x
        当前的值是i 比 x 小满足条件，但是如果g(i)<g(x)或者 g(i)=g(x)都不合法 
        */ 
        if(Num <= Max && tot >= last){
            Max = Num;
            last = tot;
        }
        return;
    }
    int mul =  1;
    for(int i=0;i<=limit;++i){
        dfs(dep+1,Num*mul,tot*(i+1),i);
        mul*=prime[dep];
        if(Num*mul>n) break;
    }
}

int main(){
    scanf("%d",&n);
    dfs(1,1,1,20);
    printf("%lld\n",Max);
    return 0;
}