金条

Posted on In

题目大意：小林在一家商店里购物，共有 i 件物品，第 i 件物品的价格为 i。小林身上带 了许多金条，每根金条的价值都为整数，价值为 1~N 的金条数量都足够多。 对于任何一件物品，小林只会用同一价值的若干金条购买它，而且不能找零。 因此，对于第 i 件物品，会有 C(i)种购买方法。小林只会选择这样的一件物品 i 进行购买：C(i) > max{ C(j) }， 1 <= j < i。 请你告诉小林，他能购买的最贵的物品的价格是多少。

看起来很麻烦其实就是求n以内的最大的反质数

有几个性质或者结论定理：

  • 1 ~ n中最大的反质数，是1 ~ n 中约数个数最多的数中最小的一个

对于ans，设任意的一个x，显然满足：

若x小于ans，则f(x)<f(ans)

若x大于ans，则f(x) <f(ans)

第一个性质说明这个ans是反质数，第二个性质说明大于ans的都不是反质数，顾ans即为所求

  • 一个数的约数的个数等于所有素因子的次数+1的乘积

\(48=2^4\times 3^1\)

因此有\((4+1)\times (1+1)\)个约数

这是显然的到道理

  • 关于反质数：x的质因子是连续的多干戈最小的质数，并且质数单调递减

记住就好

代码如下：（根绝性质dfs）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>
#define int long long
using namespace std;

int p[13] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};
int n, ans, gans;

inline void DFS(int x, int gx, int id, int cnt)
{
    if (gx == gans && x < ans) ans = x;
    if (gx > gans) ans = x, gans = gx;
    for (int i = 1; i <= cnt; i ++)
    {
        if(x * p[id] <= n)
        {
            x *= p[id];
            DFS(x, gx * (i + 1), id + 1, i);
        }
    }
    return;
}

signed main()
{
    cin >> n;
    DFS (1, 1, 1, 20);
    cout << ans << '\n';
    return 0;
}