基础数学算法-反素数

题目-反素数

问题分析

相当于求的是约数个数最多的最小的数字, 约数个数最多保证了$g(x)>g(i)$, 并且后面的数字$k$的约数个数$g(k)\ge g(x)$, 反素数的定义是严格大于, 因此两方面限制了反素数就是约数个数最多的最小的数字

分析$g$函数的性质

• $int$范围内的质因子数量很少, 质数从$2$乘到$29$, 结果是$6469693230$, 质数的个数只有$10$个
• $int$范围内质因子的最大次数是$31$, 因为$2^{31}=2147483648$超过了$int$范围
• 分解质因数的结果$2^{c_1}{3}^{c_2}...p^{c_k}$, 有$c_1\ge c2\ge ...\ge c_k$, 反证法, 假设$p_i<p_j$并且$c_i<c_j$, 因为约数个数是$(c_i+1)(c_j+1)$, 对约数个数会产生影响, 交换两个位置的质数, 约数个数不变, 得到的数字更小, 因此有$c_1\ge c2\ge ...\ge c_k$

因此可以$dfs$搜索反素数

算法步骤

设计$dfs$函数, 从第一个素数开始遍历, 记录当前用到了哪个素数, 以及得到的数字$ans$, 产生的约数个数$\Pi (c_k+1)$, 上一个素数的使用次数

注意: 在$dfs$过程中, 如果发现curr * primes[u] > n那么直接返回即可, 因为是curr是累乘的, 当前失败, 后面的也一定失败

在$dfs$过程中, curr *= primes[u]之后, 回溯的过程中, 不需要curr /= primes[u], 因为需要累乘

算法时间复杂度$O(\log n^k)$, $k$是素数的个数

代码实现

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int primes[9] = {
   2, 3, 5, 7, 11, 13, 17, 19, 23};

int n;
int max_cnt, ans;

void dfs(int u, int curr, int last, int cnt) {
   
    if (cnt > max_cnt || (cnt == max_cnt && curr < ans)) {
   
        ans = curr;
        max_cnt = cnt;
    }

    if (u == 9) return;

    for (int i = 1; i <= last; ++i) {
   
        if ((LL) curr * primes[u] > n) return;
        curr *= primes[u];
        dfs(u + 1, curr, i, cnt * (i + 1));
    }
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n;

    dfs(0, 1, 30, 1);

    cout << ans << '\n';

    return 0;
}