B 签到

题意

有 $n \times m$ 个口罩，你可以将 $x$ 个口罩包装为一盒，把多盒口罩包装为一箱。请问，怎么确定口罩盒的规格 $x$，可以分配 $n$ 个口罩在 $m$ 个箱子中，且可以分配 $m$ 个口罩在 $n$ 个箱子中。要求使用口罩盒的数量最小，且方案的字典序最大。

思路

通宵后，脑子真滴会很糊，那么简单的题竟然想不到。

假设 $n \le m$，为了满足：

  1. 可以分配 $m$ 个箱子, 每个箱子 $n$ 个口罩
  2. 可以分配 $n$ 个箱子, 每个箱子 $m$ 个口罩

由于每个盒子口罩数最多为 $n$，我们构建 $n$ 个口罩盒，每个口罩盒里有 $n$ 个口罩。

我们只需要剩下的口罩盒满足：

  1. 可以分配 $n$ 个箱子, 每个箱子 $m - n$ 个口罩
  2. 可以分配 $m - n$ 个箱子, 每个箱子 $n$ 个口罩

这显然是一个递归的过程，时间复杂度 $O(n)$

代码

#include <bits/stdc++.h>
using namespace std;

vector<int> ans;

void dfs(int n, int m) {
    if (!n || !m) return;
    if (n > m) swap(n, m);
    for (int i = 0; i < n; ++i) ans.emplace_back(n);
    dfs(n, m - n);
}

int main() {
    int t, n, m;
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d", &n, &m);
        ans.clear();
        dfs(n, m);

        printf("%llu\n", ans.size());
        for (int x: ans)
            printf("%d ", x);
        puts("");
    }
    return 0;
}