2021牛客暑期多校训练营5 G、Greater Integer, Better LCM

题目大意

给你，你要让的前提下，最小的是什么，并且给出的是分解质因数的形式，。

Solution

考点：二进制枚举

看到这个给的这么形式化，就要围绕这个去弄，而且幂次之和不超过，很明显的让我们去二进制枚举。

那么我们就可以暴力的预处理出当前状态，可以的全部花费，那么要更新还有一个前提，就是之前的最起码应该大于，才可以更新前半部分，大于才可以更新后半部分，我们这样暴力乱搞之后对于花费大于的全部状态的最小花费都可以找出来。

接下来我们只需要再把这些东西的子集更新一下，注意因为我们乱搞的时候有一个的条件，可能这个状态就无法大于等于，这时候保留的仍然是一个无穷大的值，但是我们用这个状态更新应该可以由转移来的，所以我们要倒序的枚举一下子集，保证每个状态都找到最小值。

接下来去枚举这个幂次，左右怎么分保证个数都是的最小值了。

找出这个最小值，再减掉就是最终答案了。

#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
inline __int128 read() { __int128 s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(__int128 x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; __int128 tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }
const int N = (1<<18) + 7;
int n, m;
int p[20], q[20];
__int128 fa[N], fb[N], a, b, c;

void dfs(int dep, __int128 prod, int s) {
    if (dep == n) {
        if (prod >= a)    fa[s] = min(fa[s], prod);
        if (prod >= b)    fb[s] = min(fb[s], prod);
        return;
    }
    for (int i = 0; i <= q[dep]; ++i) {
        if (i == q[dep])    s |= (1 << dep);
        dfs(dep + 1, prod, s);
        prod *= p[dep];
    }
}

int solve() {
    n = read();
    m = (1 << n) - 1;
    for (int i = 0; i < n; ++i) {
        p[i] = read(), q[i] = read();
    }
    a = read(), b = read(), c = 1;

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < q[i]; ++j)    c *= p[i];
    }

    __int128 inf = c * 2;

    ms(fa, 0x3f), ms(fb, 0x3f);
    dfs(0, 1, 0);

    for (int i = m; i >= 1; --i) {
        for (int j = 0; j < n; ++j) {
            if (i & (1 << j)) {
                fa[i ^ (1 << j)] = min(fa[i ^ (1 << j)], fa[i]);
                fb[i ^ (1 << j)] = min(fb[i ^ (1 << j)], fb[i]);
            }
        }
    }

    __int128 res = inf;
    for (int i = 0; i <= m; ++i) {
        res = min(res, fa[i] + fb[i ^ m]);
    }
    print(res - a - b);

    return 1;
}