题意

对于任何正整数 x,其约数的个数记作 g(x)。例如 g(1)=1g(6)=4

如果某个正整数 x 满足:\forall 0 \lt i \lt x,都有 g(x) \gt g(i),则称 x 为反质数。例如,整数 1,2,4,6 等都是反质数。

求不超过 N 的最大的反质数

思路

考虑唯一分解定理分解一个数 x

x = \prod p_i^{c_i}

其中 p_i 为质数,且单调递增。

其约数和即为 \prod(c_i+1)

注意到 c_i 一定单调递减,因为如果不满足单调减的话可以通过调整法找到更优解。所以一个数是反素数的必要条件是 c_i 单调递减。

而且,注意到最小的十一个素数乘积大于 2\times 10^9,所以只需要最前面的几个素数。同时如果只包含最小的素数,2^{31}\gt2\times 10^9,所以指数只用枚举到 30

所以直接 dfs,找到约数个数最多的数中最小的一个(因为要 \forall 0 \lt i \lt x)。

#include <cstdio>

typedef long long ll;
const ll prime[] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};

ll n, ans, maxcnt;

void dfs(int now, ll nowprod, ll nowcnt, int nowlim)
{
    if (nowcnt > maxcnt || (nowcnt == maxcnt && nowprod < ans))
    {
        ans = nowprod;
        maxcnt = nowcnt;
    }
    for (ll i = 1, t = prime[now]; i <= nowlim && t * nowprod <= n; ++i, t *= prime[now])
        dfs(now + 1, nowprod * t, nowcnt * (i + 1), i);
}

int main()
{
    scanf("%lld", &n);
    ans = 1, maxcnt = 1;
    dfs(1, 1, 1, 30);
    printf("%d\n", ans);
    return 0;
}
最后修改日期:2020年12月22日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。