自动搬运

查看原文

来自洛谷，原作者为

	dehsirehC 一个人的命运啊，

搬运于2025-08-24 23:04:01，当前版本为作者最后更新于2024-09-03 23:23:01，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

下面会介绍两种做法，希望大家不要火大。

首先考虑当 $m<n$ 时显然无解，接下来就不再考虑这种情况了。

由于 $m\ge n$ ，故对于任意 $1\le i\le j\le n$ ，区间 $[\frac{m(i-1)}{j},\frac{mi}{j})$ 中必定存在整数。

对于所有 $0\le i<j\le n$ ，我们称 $\lceil\frac{mi}{j}\rceil$ 为关键点，特别的，我们认为 $m$ 也是关键点。

我们将所有关键点去重并排序后得到序列 $b_0,b_1,\cdots,b_k$ 。

容易发现 $b$ 中相邻两数组成的区间 $[b_i,b_{i+1})$ 内的数是没有本质区别的。

换句话说，我们只需要考虑 $a_i$ 为 $b_0,b_1,\cdots b_{k-1}$ 这 $k$ 个数的情况即可。

此时写一个暴搜可以发现， $n$ 从 $18$ 开始就必定无解了，正经证明我哪会。

（我写的搜索在本地只需要跑 2min 左右）

由于 $T$ 比较大，故可以将 $n$ 在 $1\sim 17$ 之间的所有解先搜出来，再每组询问暴力判断。

具体的，把问题看成 $m=1$ 且 $a_i$ 为实数时的情况，关键点与 $a_i$ 用分数表示。

而原问题本质就是让一些关键点区间不能选（没有整数点），故判断就看是否所有区间都能选即可。

不过现在还有一个问题，就是预处理搜出所有合法的解太慢了，而由于解数太多所以也无法打表。

但是容易发现真正会用到的解数可能并不多，故直接把这些解打表即可。

而找会用到的解直接把 $m$ 比较小的全跑一遍即可，可以证明当 $m\ge n(n-1)$ 时 $a_i$ 是整数与实数没有区别，换句话说，只需要考虑 $n\le m\le n(n-1)$ 时会用到的解即可。

（我写的打表程序在本地只需要跑 1min 左右）

标程在没有压代码长度的情况下只有不到 $30\text{KB}$ ，可以说还是很短的。

下面是暴搜所有合法的解并判断的一种实现方式：

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
const int M = 1e8;
int T, m, n, num, a[100], f[100][100];
int l[20][20], r[20][20], p[20], s[20];
pair<int, pair<int, int>> A[100];
vector<vector<pair<pair<int, int>
, pair<int, int>>>> v[20];
void dfs(int now) {
    if (now > n) {
        vector<pair<pair<int, int>
        , pair<int, int>>> V(n);

        for (int i = 1; i <= n; i++) {
            V[i - 1] = {A[p[i]].second,
                        A[p[i] + 1].second
                       };
        }

        v[n].emplace_back(V);
        return;
    }

    unsigned int S = 0;

    for (int i = 1; i < now; i++) {
        S |= 1 << s[i] * now / M;
    }

    int t = __lg((~S) & -(~S));

    for (int i = l[now][t]; i <= r[now][t]; i++) {
        bool flag = 1;

        for (int j = 1; j < now; j++) {
            if (f[i][p[j]] > now) {
                flag = 0;
                break;
            }
        }

        if (flag) {
            s[now] = a[p[now] = i];
            dfs(now + 1);
        }
    }
}
inline void init(int n) {
    if (!v[n].empty()) {
        return;
    }

    num = 0;

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            if (__gcd(i, j) == 1) {
                A[++num] = {(M * j + i - 1) / i, {i, j}};
            }
        }
    }

    sort(A + 1, A + num + 1);

    for (int i = 1; i <= num; i++) {
        a[i] = A[i].first;
    }

    A[num + 1].second = {1, 1};

    for (int i = 1; i <= num; i++) {
        f[i][i] = n + 1;

        for (int j = i + 1; j <= num; j++) {
            f[i][j] = 0;

            for (int k = n; k; k--) {
                if (a[i]*k / M == a[j]*k / M) {
                    f[i][j] = k;
                    break;
                }
            }

            f[j][i] = f[i][j];
        }
    }

    memset(l, 0x3f, sizeof(l));
    memset(r, 0, sizeof(r));

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= num; j++) {
            int t = a[j] * i / M;
            l[i][t] = min(l[i][t], j);
            r[i][t] = max(r[i][t], j);
        }
    }

    dfs(1);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> T;

    while (T--) {
        cin >> n >> m;

        if (n >= 18 || n > m) {
            cout << "fire big\n";
            continue;
        }

        init(n);
        bool flag = 0;

        for (int i = 0; i < v[n].size(); i++) {
            flag = 1;

            for (int j = 0; j < n; j++) {
                int x = v[n][i][j].first.first;
                int y = v[n][i][j].first.second;
                int X = v[n][i][j].second.first;
                int Y = v[n][i][j].second.second;

                if ((m * y + x - 1) / x == (m * Y + X - 1) / X) {
                    flag = 0;
                    break;
                }
            }

            if (flag) {
                for (int j = 0; j < n; j++) {
                    int x = v[n][i][j].first.first;
                    int y = v[n][i][j].first.second;
                    cout << (m * y + x - 1) / x << " ";
                }

                cout << '\n';
                break;
            }
        }

        if (!flag) {
            cout << "fire big\n";
        }
    }

    return 0;
}

接下来介绍另一种做法，考虑增量法。

找出 $n=17$ 时的所有关键点，考虑将 $a_i$ 描述为关键点的区间，而不是某个关键点。

假设现在得到了 $n=x-1$ 时的所有解，考虑拓展得到 $n=x$ 时的所有解，即考虑 $a_x$ 是什么。

枚举 $a_x$ 在 $x$ 段中的哪一段，即枚举整数 $1\le j\le x$ 满足 $a_x\in [\frac{m(j-1)}{x},\frac{mj}{x})$ 。

而对于 $a_{1\sim x-1}$ ，将它们从小到大排序（区间不交）后即可得到它们在 $n=x\to x+1$ 时的限制。

将之前对应的关键点区间与新限制对应的关键点区间取交即可，若存在交为空则增量失败。

由于 $m\ge n(n-1)$ 时任意解均合法，故只需要考虑 $n\le m<n(n-1)$ 时的情况。

设 $f_i$ 表示 $n=i$ 时上述算法得到的解的数量，则该算法总时间复杂度即为 $O(\sum_{i=1}^{17} f_ii^3+17T)$ 。

实践得到上式约为 $1.6\times 10^8$ ，若在过程中将解去重，则上式只有约 $3\times 10^7$ ，都跑得很快。

顺带一提，上述做法如果不对询问记忆化的话时间复杂度是可以达到 $O(\sum_{i=1}^{17} f_ii^3+T\max_{i=1}^{17} f_ii)$ 的，不过由于出题人非常良心，并没有卡不记忆化的做法（即一种询问 $(n,m)$ 不会出现特别多次）。

如果你使用了其它的做法通过了此题，欢迎联系我。