反素数

分解质因数 约数个数 DFS T3 P1463 [POI2001][HAOI2007] 反素数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目描述

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

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

现在给定一个数 $N$，你能求出不超过 $N$ 的最大的反质数么？

输入格式

一个数 $N$。

输出格式

不超过 $N$ 的最大的反质数。

样例 #1

样例输入 #1

1000

样例输出 #1

840

提示

$1\le N\le 2\times 10^9$

思路

一个数是反素数的条件是在 $i<x$ 中不存在 $g(i)\ge g(x)$ , 即 x 的约数个数是最大的。

而又因为 x 要是最大的, 因此结果就是 1到n 中约数个数最大的数。

对于 2e9 这个范围, 其不同的质因数也是很有限的, 可以尝试 $2\times 3\times 5\times \dots$ 看看什么时候超 2e9, 实践后发现仅仅乘到 29 就已经是 6e9 了, 故最多只会乘到 23, 也就是用到 9 种质因子。

即第一个性质：不同的质因子最多会有9种

第二个性质：每个质因子的次数最大也是30, 即 $2^{30}$。

我们只关心约数个数, 因此分解质因数后的底数是什么无所谓, 只需要确保指数正确就行。

因此第三个性质：所有质因子的次数一定递减。假如存在质因子分解 $3^5\times 5^3$ , 对于结果来说与 $3^3\times 5^5$ 是一样的。

至此, 一个显而易见的方法就浮出水面了, 直接DFS爆搜。

搜索每个质因子的次数即可。DFS函数中传入 当前搜到第几个质数, 上一个的次数, 当前值, 以及约数个数。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
 
int n, res, number;
 
int primes[] = {2, 3, 5, 7, 11, 13, 17, 19, 23};
 
void dfs(int u, int last, int now, int ans)
{
    if (ans > res || ans == res && now < number)
    {
        res = ans;
        number = now;
    }
    if (u == 9)
        return;
    for (int i = 1; i <= last; i++)
    {
        if ((LL)primes[u] * now > n)
            break;
        now = primes[u] * now;
        dfs(u + 1, i, now, ans * (i + 1));
    }
}
 
void solve()
{
    cin >> n;
    dfs(0, 30, 1, 1);
    cout << number << endl;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}