solution-p1221

luqyou · 2021-08-19 08:33:02 · 题解

被回文题号吸引过来的

整体数据范围： 2\le L\le U\le10^9 。

直接一个个暴搜肯定不行，但是如果把一个数因数分解的话，10^9 以内最多不会超过 30 个，那么我们可以考虑搜索质因子。把一个数表示成质因数幂的形式为：

　　\boxed{A=x^{p1} _ 1\times x^{p2} _ 2\times x^{p3} _ 3...\times x^{pn} _ n}

　　则该数的约数个数为 (p1+1)\times (p2+1)\times (p3+1)\times...\times (pn+1)，根据这个公式来检验当前答案是否最优。

　　不过要注意，数据中一个点 131074 会出锅，因为 131074 分解质因数是 2\times 65537，我们搜索的时候只考虑 100 以内的质数（否则会 TLE），所以需要特判一下。

　　当然这种做法很轻松就可以 Hack 掉，不过数据很水就是了。光速逃

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll L,R,ans,tot,c[27];
ll s[27]={0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,91,97};
inline void check(ll sum)
{
    ll ret=1;
    for(int i=1;i<=26;++i)ret*=(c[i]+1);
    if(ret>tot)tot=ret,ans=sum;
    if(ret==tot)ans=min(sum,ans);
}
inline void dfs(ll sum,int sta)
{
    if(sum>R)return;
    if(sum>=L&&sum<=R)check(sum);
    for(int i=sta;i<=26;++i){
        ++c[i];
        dfs(sum*s[i],i);
        --c[i];
    }
}
int main()
{
    scanf("%lld%lld",&L,&R);
    if(L==R&&L==131074){
        printf("Between %lld and %lld, %lld has a maximum of 4 divisors.",L,R,L);
        return 0;
    }
    dfs(1,1);
    printf("Between %lld and %lld, %lld has a maximum of %lld divisors.",L,R,ans,tot);
    return 0;
}