hihoCoder #1072 辅导

题意

$\DeclareMathOperator{\lcm}{lcm}$选 $k$ （$k\le 10$）个 $1$ 到 $n$（$n\le 10^9$）之间的整数（可以相同），使得 $\lcm(a_1, \dots, a_k)$ 最大。

题解

这是 hihoCoder 挑战赛 #6 的 B 题，CLJ（WJMZBMR）出的。CLJ 的题解：

首先我们注意到，如果你选择了两个不互质的 $a, b$，那么不妨把 $a$ 换成 $a/(a,b)$。显然 LCM 还是不变的。

这意味着存在一组最优解使得所有选择的数都两两互质。

那么我们不妨使用暴搜，首先我们注意到我们至少可以选择比 $n$ 小的最大的 $k$ 个质数来当做初始解。

然后我们从大到小枚举是否使用，搜到 $x$ 时，假如当前最优解是 $ans$, 当前 LCM 是 $w$，如果还能选择 $t$ 个，假如 $wx^t \le ans$，那么显然已经无法得出更优的解了，就可以剪枝了。

首先需要指出，上面题解中

如果你选择了两个不互质的数 $a, b$，那么不妨把 $a$ 换成 $a/(a,b)$ 。显然 LCM 还是不变的。

这个结论是错误的，很容易举出反例：$a=4, b=2$，可能是作者笔误。不过，对于不互质的两个数 $a,b$ ，确实存在两个互质的数 $a',b'$ （$a'\le a, b'\le b$），使得 $\lcm(a',b') = \lcm(a,b)$。

写出 $a, b$ 两数的质因子展开式，设

$$

\begin{align}

a = p_1^{i_1} p_2^{i_2}\dots p_n^{i_n} \notag\

b = p_1^{j_1} p_2^{j_2}\dots p_n^{j_n} \notag

\end{align}

$$

在 $a$，$b$ 展开式中，只保留幂次较大的项便得到了 $a'$, $b'$。

至此，我遇到了一个困难：如何求比 $n$（$n\le 10^9$）小的最大的 $k$（$k\le 10$）个素数？

当然，求出 $k$ 个最大的素数并非我们的最终目的，这样做只是为了得到一个较大的初始解，求出不满 $k$ 个最大的素数也无妨，从而我们可以暴力判断后若干（比如 100）个数。另外，应当能看出初始解是否取一个较大的值，对程序运行时间影响并不大，将其取为 $n$ 甚至 $0$ 也可以。

复杂度

？？从递归深度开始考虑？？（大误，递归深度最大即为 $k$ 啊！！！我真是沙茶）

Implementation

#include <bits/stdc++.h>

using namespace std;

vector<int> a;

long long res;

long double product;

const int mod = 1e9 + 7;

int n, k;

void dfs(int x, long double cur_prod){

    if(a.size() == k || x == 1){

        // product = cur_rod;

        res = 1;

        product = cur_prod;

        for(auto i: a){

            // product *= i;

            res *= i, res %= mod;

        }

        return;

    }

    if(cur_prod * pow((long double)x, k - a.size()) <= product)

        return; // 剪枝

    bool flag = true;

    for(auto i: a)

        if(__gcd(x, i) != 1){

            flag = false;

            break;

        }

    if(flag){

        a.push_back(x);

        dfs(x-1, cur_prod * x);

        a.pop_back();

    }

    dfs(x-1, cur_prod);

}

int main(){

    // int n, k;

    cin >> n >> k;

    // product = n == 1 ? n : n * (n - 1);

    product = n;

    res = n;

    dfs(n, 1);

    cout << res << endl;

    return 0;

}

上面代码中的 dfs() 还有一种写法：

void dfs(int x, long double cur_prod){

    if(a.size() == k || x == 1){

        res = 1;

        product = cur_prod;

        for(auto i: a){

            res *= i, res %= mod;

        }

        return;

    }

    for(int i = x; ; i--){

        bool flag = true;

        for(auto j: a){

            if(__gcd(i, j) != 1){

                flag = false;

                break;

            }

        }

        if(!flag) continue;

        if(cur_prod * pow((long double)i, k - a.size()) <= product)

            break;

        a.push_back(i);

        dfs(i, cur_prod * i);

        a.pop_back();

    }

}

巴特西

hihoCoder #1072 辅导

题意

题解

复杂度

Implementation

最新文章

热门文章