F. Multicolored Markers 题解

一、题目回顾

有 $a$ 个红色格子和 $b$ 个蓝色格子，总共 $a+b$ 个格子。要求：

1. 所有格子拼成一个矩形（面积为 $a+b$）。
2. 至少一种颜色的格子自身也拼成一个矩形（即该颜色的所有格子形成一个子矩形）。

在所有满足条件的方案中，求该矩形的最小周长。

数据范围：$1 \le a, b \le 10^{14}$。

二、问题分析

设总矩形面积为 $S = a + b$，边长为 $W \times H$（$W \le H$），周长为 $2(W+H)$。

不妨假设红色格子形成矩形（另一种情况是对称的，最后对 $a,b$ 互换取最小值即可）。设红色矩形的边长为 $w \times h$（$w \le h$），则一定有：

• $w \cdot h = a$
• 红色矩形可以放入总矩形中：$w \le W$ 且 $h \le H$（红色矩形可以旋转，因此也可以是 $h \le W$ 且 $w \le H$，但因为我们要求 $w \le h$ 且 $W \le H$，所以只需考虑 $w \le W$ 且 $h \le H$）

对于固定的总矩形 $W \times H$，我们希望知道是否存在红色矩形的分解 $w \times h = a$ 满足 $w \le W$ 且 $h \le H$。

三、算法流程

3.1 枚举总矩形

枚举 $W$ 从 $1$ 到 $\lfloor\sqrt{S}\rfloor$，当 $S \bmod W = 0$ 时，取 $H = S / W$，得到一组总矩形分解。

3.2 判断红色矩形是否可放入

对于给定的 $W$，我们需要判断是否存在 $w \mid a$ 使得 $w \le W$ 且 $a/w \le H$。

等价于：找到一个 $w$ 使得 $w \le W$ 且 $w \ge a / H$（由 $a/w \le H$ 推出 $w \ge a/H$）。因此我们需要在 $a$ 的因子中，找一个落在区间 $[\lceil a/H \rceil, W]$ 内的因子。

实际上，因为 $H = S/W$ 随 $W$ 增大而减小，条件 $a/w \le H$ 随着 $W$ 增大变得更容易满足（$H$ 变小会收紧条件？仔细看：$W$ 增大 → $H$ 减小 → 要求 $a/w \le H$ 更严格，所以其实更大的 $W$ 对红色矩形的宽度约束更紧）。我们需要在 $W$ 增长的过程中维护可行的 $w$。

关键观察：对于固定的 $W$，我们只需要考虑最大的满足 $w \le W$ 的 $a$ 的因子。因为当 $w$ 越大，$h = a/w$ 越小，条件 $h \le H$ 越容易满足。因此检查那个最大的 $w$ 即可。

3.3 双指针快速判定

预处理出 $a$ 的所有因子（只存 $\le \sqrt{a}$ 的部分），排序为数组 $d[0 \dots k-1]$。

枚举 $W$ 递增，用指针 $p$ 指向当前的最大因子满足 $d[p] \le W$。因为 $W$ 单增，指针也可以单增。

对每个合法的 $W$，检查 $a / d[p] \le H$。若满足，则用周长 $2(W+H)$ 更新答案。

3.4 对称处理

以上假设红色形成矩形。蓝色形成矩形的情况只需交换 $a,b$ 再跑一遍，取最小周长。

四、复杂度分析

• 预处理因子：$O(\sqrt{\max(a,b)})$。
• 枚举总矩形边长：$O(\sqrt{S})$。
• 双指针均摊 $O(\text{因子个数})$，小于 $O(\sqrt{a})$。

总时间复杂度 $O(\sqrt{a} + \sqrt{b} + \sqrt{a+b})$，在 $a,b \le 10^{14}$ 时可轻松通过。

五、参考代码

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

typedef long long li;

const int N = 1000000; // 1e6, 足够存放 sqrt(1e14) 内的因子
int lens[N];
int k;

// 假设颜色 a 形成矩形，b 为另一种颜色
li solve(li a, li b) {
    k = 0;
    // 枚举 a 的因子（只存 ≤√a 的部分）
    for (li i = 1; i * i <= a; ++i)
        if (a % i == 0)
            lens[k++] = i;

    li ans = 2 * (a + b) + 2;   // 初始化为一个极大的周长
    li S = a + b;
    int p = 0;

    // 枚举总矩形的一边 W
    for (li W = 1; W * W <= S; ++W) {
        if (S % W != 0) continue;
        li H = S / W;

        // 移动指针到满足 lens[p] <= W 的最大因子
        while (p + 1 < k && lens[p + 1] <= W)
            ++p;

        // 检查另一边是否也放得下
        if (a / lens[p] <= H)
            ans = min(ans, 2 * (W + H));
    }
    return ans;
}

int main() {
    li a, b;
    scanf("%lld%lld", &a, &b);
    // 分别假设红色或蓝色形成矩形
    printf("%lld\n", min(solve(a, b), solve(b, a)));
    return 0;
}