高合成数的 2 道入门题目

whhsteven · 2021-07-02 08:19:57 · 个人记录

什么是高合成数？

高合成数（Highly Composite Number），常见又称「反素数」，是指满足 \forall 0 < i < n 有 g(i) < g(n) 的 n，其中 i,n \in \mathbb N^+，g(n) 表示 n 的约数个数。

重要结论

对于高合成数 n，作质因子分解：

这里 p_1 < p_2 < \cdots < p_k，则必然有 \alpha_1 \geq \alpha_2 \geq \cdots \geq \alpha_k。

这是因为，如果 n 存在质因子 p_i,p_j，且 p_i < p_j,\ p_i^{\alpha_i}||n,\ p_j^{\alpha_j}||n,\ \alpha_i < \alpha_j，则交换 \alpha_i 和 \alpha_j 之后 g(n) 显然不变，而 n 会变小。从而，只有质因子递增时指数严格不增才可能是高合成数。

另外需要注意：上面的约束只是必要条件，不是充分条件。

P1463 [POI2002][HAOI2007]反素数

题目链接

P1463

题意简述

给定 N，求不超过 N 的最大高合成数。

解

DFS 查找。

#include<bits/stdc++.h>
#define REG register

using namespace std;

namespace acah
{
    typedef long long ll;

    const int pc = 12;
    const int pr[13] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};

    ll N, ans, maxc;

    void dfs(ll cur, ll cd, int p, int tb) // cur_val, cur_divisor, cur_prime, time_bound
    {
        if(cd > maxc || (cd == maxc && cur < ans)) maxc = cd, ans = cur;
        for(REG int i = 1; i <= tb; i++) {
            cur *= pr[p];
            if(cur > N) break;
            if(p < pc)
                dfs(cur, cd * (i + 1), p + 1, i);
        }
    }

    int work()
    {
        scanf("%lld", &N);
        dfs(1ll, 1ll, 1, 32);
        printf("%lld", ans);
        return 0;
    }
}

int main() {return acah::work();}

P1574 超级数

题目链接

P1574

题意简述

给定一组数 a_1 \sim a_n，求不超过 a_1 \sim a_n 的最大高合成数分别是多少。

解

同样 DFS 查找。

与 P1463 不同的是，由于需要回答多组询问，可以在 DFS 时只考虑上面所述的必要条件，算出数据范围内所有可能为高合成数的数，然后由小到大判断每一个数的约数个数是否严格大于上一个高合成数，回答询问时在最终序列中二分查找即可。

#include<bits/stdc++.h>
#define REG register

using namespace std;

namespace acah
{
    typedef long long ll;

    const int pc = 16;
    const int pr[17] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53};
    const int maxn = 1e5 + 7;

    int N;
    ll bd, a[maxn];
    ll curd;

    struct P {
        ll v, d;
        P() {}
        P(ll _v, ll _d) {v = _v, d = _d;}
        const bool operator < (const P &th) const
        {return v < th.v;}
    };

    vector<P> prob;
    vector<P>::iterator it;
    vector<ll> ans;

    template<typename T> inline void qread(T &x)
    {
        x = 0; REG int t = 0; REG char ch = getchar();
        while(!isdigit(ch)) t |= (ch == '-'), ch = getchar();
        while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
        x = t ? -x : x;
    }

    template<typename T> inline void tomax(T &a, T b)
    {a = a < b ? b : a;}

    void dfs(ll cur, ll cd, int p, int tb)
    {
        prob.push_back(P(cur, cd));
        for(REG int i = 1; i <= tb; i++) {
            cur *= pr[p];
            if(cur > bd) break;
            if(p < pc)
                dfs(cur, cd * (i + 1), p + 1, i);
        }
    }

    int work()
    {
        qread(N);
        for(REG int i = 1; i <= N; i++) qread(a[i]), tomax(bd, a[i]);
        dfs(1l, 1l, 1, 66);
        sort(prob.begin(), prob.end());
        for(it = prob.begin(); it != prob.end(); it++) if(it -> d > curd)
            curd = it -> d, ans.push_back(it -> v);
        for(REG int i = 1; i <= N; i++)
            printf("%lld\n", *(upper_bound(ans.begin(), ans.end(), a[i]) - 1));
        return 0;
    }
}

int main() {return acah::work();}

上面的代码开了 O2 之后跑到了目前的最优解。（似乎比没开快读的打表还快……）

附赠

前 20 个高合成数。