E

观察数据范围，容易想到二分答案。

那么问题转化为如何统计 $1 \sim k$ 中的美丽数的数量。

考虑 $1 \sim k$ 中有多少个数能被 $p$ 整除，答案显然是 $\lfloor k/p \rfloor$。

考虑 $1 \sim k$ 中有多少个数能被 $p$ 和 $q$ 整除，答案是 $\lfloor k/p \rfloor + \lfloor k/q \rfloor$ 吗？

不对，因为这样的话，能同时被 $p$ 和 $q$ 整除的数会被算两次。所以要减去能同时被 $p$ 和 $q$ 整除的数，也就是减去 $\lfloor k / \text{lcm}(p,q)\rfloor$。

考虑 $1 \sim k$ 中有多少个数能被 $p$ 或 $q$ 整除，那么就是再减去能被 $p$ 和 $q$ 同时整除的数。

所以 $1 \sim k$ 中美丽数的数量就是 $\lfloor k / p \rfloor + \lfloor k / q \rfloor - 2\lfloor k/\text{lcm}(p,q)\rfloor$。

这样我们就可以直接二分得到最后的答案。

#include <iostream>
#define int long long
using namespace std;

int check (int p, int n, int m, int g)
{
    return p / n + p / m - p / g * 2;
}

int gcd (int a, int b)
{
    if (!b) return a;
    return gcd (b, a % b);
}

signed main (void)
{
    int t;


    cin.tie(0)->sync_with_stdio (false);
    cin >> t;
    while (t--) {
        int n, m, k;

        cin >> n >> m >> k;
        int g = n / gcd (n, m) * m;
        int l = 1, r = 1e18, mid, ans = -1;
        while (l <= r) {
            mid = (l + r) / 2;
            if (check (mid, n, m, g) < k) l = mid + 1;
            else r = (ans = mid) - 1;
        }
        cout << ans << '\n';
    }
    return 0;
}

F

考虑这其实和背包问题很像，只是本题有多个“价值”。

然而价值都很小（最大为 $6$），那么我们可以直接把它放到我们的 DP 状态里。

所以最终的状态就是：$f_{iabcdef}$，表示考虑了前 $i$ 种学习计划，每种科目的得分分别为 $a, b, c, d, e, f$。

其实还有更简单的写法：把 $abcdef$ 压到同一个整数里，也就是用一个六进制数来作为状态。

转移和背包问题是一样的。

#include <bits/stdc++.h>

using i64 = long long;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int N, K, P;
    std::cin >> N >> P;
    K = 6;

    std::vector<int> pw(K + 1);
    pw[0] = 1;
    for (int i = 1; i <= K; i++) {
        pw[i] = pw[i - 1] * (P + 1);
    }

    std::vector dp(pw[K], -1LL);
    dp[0] = 0;

    for (int i = 0; i < N; i++) {
        int C;

        std::vector<int> A(K);
        for (int j = 0; j < K; j++) {
            std::cin >> A[j];
        }
        std::cin >> C;

        for (int s = pw[K] - 1; s >= 0; s--) {
            int t = 0;
            for (int j = 0; j < K; j++) {
                int a = s / pw[j] % (P + 1);
                int na = std::min(P, a + A[j]);
                t += na * pw[j];
            }
            if (dp[s] != -1 && (dp[t] == -1 || dp[t] > dp[s] + C)) {
                dp[t] = dp[s] + C;
            }
        }
    }
    std::cout << dp.back() << "\n";

    return 0;
}