不知道为什么自己的程序是对的。

Problem

数学家们喜欢各种类型的有奇怪特性的数。例如，他们认为 945 是一个有趣的数，因为它是第一个所有约数之和大于本身的奇数。

为了帮助他们寻找有趣的数，你将写一个程序扫描一定范围内的数，并确定在此范围内约数个数最多的那个数。不幸的是，这个数和给定的范围的都比较大，用简单的方法寻找可能需要较多的运行时间。所以请确定你的算法能在几秒内完成最大范围内的扫描。

Solution

我们一开始以为这是道错题。
我们用以下几组数据叉了绝大多数网上的正解：

998244353 998244353
998244353 998244354
998244353 998254354
998244352 998244353

直到我看到这篇博客：
https://blog.csdn.net/QQ604666459/article/details/78434074

但很遗憾它的999999999 1000000000跑出来的是错解。

于是我将它做了如下的改动，保证了其复杂度，上面也得出来正解了，但无法严格证明剪枝的正确性。

欢迎留言讨论。

UPD

上方第三组数据把该程序叉了
可喜可贺
答案为 576

// Code by ajcxsu
// Problem: most yinzi

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N=4e4;
int pri[N], p;
bool npri[N];
ll L, U, D, P;

void dfs(int pidx, ll num, ll dv, ll low, ll up, ll last) { // low-up 接下来因数之积的范围
    if(num>=L) // 可能会出现num包含非质因数的情况，但对质因数造成了浪费，最终会被最优解取代
        if(dv>D || (dv==D && num<P)) D=dv, P=num;
    if(low==up && low>num)
        dfs(pidx, num*low, dv*2, 1, 1, last); // 不管怎样先不忽略low可能为大质数的可能性
    ll ndv, nlow, nup, nnum, cnt;
    for(int i=pidx;i<p;i++) {
        if(pri[i]>up) break;
        ndv=dv, nlow=low-1, nup=up, nnum=num, cnt=1;
        while(1) {
            ndv+=dv, nnum*=pri[i], nlow/=pri[i], nup/=pri[i];
            cnt++;
            if(nlow==nup || cnt>last) break;
            dfs(i+1, nnum, ndv, nlow+1, nup, cnt); // nlow/(pri[i]^cnt) 向上取整
        }
        if(dv*(2<<cnt)<D) {
            break;
        } // 玄学剪枝，没有严格证明
    }
}

int main() {
    scanf("%lld%lld", &L, &U);
    npri[0]=npri[1]=1;
    for(int i=2;i<N;i++) {
        if(!npri[i]) pri[p++]=i;
        for(int j=0;j<p && i*pri[j]<N;j++) {
            npri[i*pri[j]]=1;
            if(i%pri[j]==0) break;
        }
    }
    dfs(0, 1, 1, L, U, 1000);
    printf("Between %lld and %lld, %lld has a maximum of %lld divisors.\n", L, U, P, D);
    return 0;
}

UPD2

把我自己加的一个 sb 剪枝去掉就对了
可喜可贺

// Code by ajcxsu
// Problem: most yinzi

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N=4e4;
int pri[N], p;
bool npri[N];
ll L, U, D, P;

void dfs(int pidx, ll num, ll dv, ll low, ll up) { // low-up 接下来因数之积的范围
    if(num>=L) // 可能会出现num包含非质因数的情况，但对质因数造成了浪费，最终会被最优解取代
        if(dv>D || (dv==D && num<P)) D=dv, P=num;
    if(low==up && low>num)
        dfs(pidx, num*low, dv*2, 1, 1); // 不管怎样先不忽略low可能为大质数的可能性
    ll ndv, nlow, nup, nnum, cnt;
    for(int i=pidx;i<p;i++) {
        if(pri[i]>up) break;
        ndv=dv, nlow=low-1, nup=up, nnum=num, cnt=1;
        while(1) {
            ndv+=dv, nnum*=pri[i], nlow/=pri[i], nup/=pri[i];
            cnt++;
            if(nlow==nup) break;
            dfs(i+1, nnum, ndv, nlow+1, nup); // nlow/(pri[i]^cnt) 向上取整
        }
        if(dv*(2<<cnt)<D) {
            break;
        } // 玄学剪枝，没有严格证明
    }
}

int main() {
    scanf("%lld%lld", &L, &U);
    npri[0]=npri[1]=1;
    for(int i=2;i<N;i++) {
        if(!npri[i]) pri[p++]=i;
        for(int j=0;j<p && i*pri[j]<N;j++) {
            npri[i*pri[j]]=1;
            if(i%pri[j]==0) break;
        }
    }
    dfs(0, 1, 1, L, U);
    printf("Between %lld and %lld, %lld has a maximum of %lld divisors.\n", L, U, P, D);
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/faq.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆