G. Greater Integer, Better LCM

前言

题解有点看不懂，自己想了个比较直接的做法。

Solution

考虑和的因数是由哪些组成的，于是发现这两个数选到的最终要包含所有，所以直接考虑枚举其中一个数，那么另一个数能取的范围就是“至少包含当前数的补集的所有数”，换句话说，我们选定一个数后，这个数有哪些选满了已知，那么另一个数一定要把没选满的都选满，所以只要能预处理出“至少某几位选满时的最小值”就可以了。

这个预处理其实很简单，先直接dfs求出恰好某几位选满时的答案，然后直接SOSDP即可。

最终统计答案时的dfs和预处的dfs几乎完全一致。

中间特别注意一下选出来的数要或者。

至于复杂度，dfs的复杂度不会超过，而SOSDP的过程是，可以轻松通过。

ll num[N];
ll a, b, ans;
ll p[N], q[N], MAXN;
int n;
void dfs(int step, ll x, int S, int opt) {
    if (step > n) {
        if (opt) {
            if (x >= a)num[S] = min(num[S], x - a);
        }
        else {
            if (x < b)return;
            if (num[S ^ ((1 << n) - 1)] != MAXN)
                ans = min(ans, x - b + num[S ^ ((1 << n) - 1)]);
        }
        return;
    }
    ll now = 1;
    for (int i = 0; i <= q[step]; ++i, now *= p[step])
        dfs(step + 1, x * now, i == q[step] ? (S | (1 << step - 1)) : S, opt);
}

int main() {
    n = fast_IO::read();
    for (int i = 1; i <= n; ++i)
        p[i] = fast_IO::read(), q[i] = fast_IO::read();
    a = fast_IO::read(), b = fast_IO::read();
    MAXN = 1e30;
    for (int i = 0; i < (1 << n); ++i)num[i] = MAXN;
    dfs(1, 1, 0, 1);
    for (int i = (1 << n) - 1; ~i; --i) {
        for (int j = 0; j < n; ++j) {
            if (!((i >> j) & 1))continue;
            num[i ^ (1 << j)] = min(num[i ^ (1 << j)], num[i]);
        }
    }
    ans = MAXN;
    dfs(1, 1, 0, 0);
    fast_IO::write(ans);
    return 0;
}