题解 P1221 【最多因子数】

· · 题解

传送门

这题的思路嘛。。。。

其实就是爆搜。

首先我们要知道，一个数X可以被分解为X=2^m1∗3^m2∗5^m3∗...∗n^mk

相信聪明的大家都能理解（注：n为质数）

当分解完后，X的个数为(m1+1)∗(m2+1)∗(m3+1)∗...∗(mk+1)

根据乘法原理，选1个，2个……m1个，为啥是m1+1？还可以不选haha

我们只需把质数预处理出来，然后暴力填m1,m2,m3，……，mk即可

加上一点小剪枝

代码：（卡常大法好）

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 10005;
const int INF = 1000000007;
ll _[N],prime[N],size,ansp=INF,ansd,anss[N],l,r;
//p 素数 2 3 5 7 (第几个质因子)
//all已经搜索到的k的因子的乘积
//last上一个的p的指数 
inline void dfs(int p,ll all,ll last){
    if(l<=all&&all<=r){//满足要求
        int o=1;
        for(register int i=1;i<p;i++){//算出约数个数
            o=o*(anss[i]+1);
        }
        if(o>ansd||(o==ansd&&all<ansp)){//最小
            ansd=o;
            ansp=all;
        }
    }
    if(all>ansp) return;//最优性剪枝
    ll lin[100]={0};
    lin[0]=1;
    for(register int i=1;i<=last;i++) lin[i]=lin[i-1]*prime[p];//预处理
    for(register int i=last;i>=1;i--){//从后往前，更高效
        anss[p]=i;  
        dfs(p+1,all*lin[i],i);
    }
}
void bao_li_chu_qi_ji(){//只可会意，不可言传
    for(int i=l;i<=r;i++){
        int ret=0;
        for(int j=1;j*j<=i;j++){
            if(i%j==0) ret+=2;
            if(j*j==i) ret--;
        }
        if(ret>ansd){
            ansp=i;
            ansd=ret;
        }
    }
}
int main(){
    for(register int i=2;i<=sqrt(N);i++){//先把质数筛出来
        for(register int j=2;j*i<N;j++){
            _[i*j]=1;  
        }
    }
    for(register int i=2;i<=N;i++){ //同上
        if(!_[i]) prime[++size]=i;
    }
    scanf("%lld%lld",&l,&r);
    ll w=log(r);
    if(r-l<5000) bao_li_chu_qi_ji();//只可会意，不可言传（因为如果范围太小这种方法会gg，自己体会一下吧）
    else dfs(1,1,w);
    printf("Between %lld and %lld, %lld has a maximum of %lld divisors.\n",l,r,ansp,ansd);
    return 0;
}

跑得还是挺快的，哈哈

偷偷安利自己的blog