题解：CF1418F Equal Product

· · 题解

题解：CF1418F Equal Product

由于条件 1,2 分别只与 x,y 有关，而条件 3 却在等式两侧都有 x,y，所以将其变形为 \frac{x_1}{x_2}=\frac{y_2}{y_1}，而后发现相当于 x_1:x_2 与 y_2:y_1 的比值相同。设为 a:b，则可令 x_1=aX,x_2=bX,y_2=aY,y_1=bY。正常需要保证 \gcd(a,b)=1，但由于此题只需构造，无需计数，不用管重复统计，因此可以不管此 case。于是我们凭空干掉了条件 3。

由于我们要对每个 x_1 分别构造，显然枚举 x_1=1,2,3,\dots,n 是必要的。为与我们的转换接轨，显然要枚举当前 x_1=aX 的分解方式，因此要枚举 x_1 的每个因数 a。此时总共枚举了 \operatorname{O}(n\log n) 组 x_1=aX（调和级数），于是将 x_1,a,X 视作已知数。此时重写原条件（\geq1 这种弱智条件省略，取整是为了适应整数条件前提）：

观察到 y_1=bY 作为整体出现，而 Y 不单独出现，x_1=aX 同理，于是将 bY 换成 y_1、aX 换成 x_1 并整理得到：

  3. 隐藏条件 b\mid y_1 即 y_1 是 b 的倍数。

有用的 (b,y_1) 共有 \operatorname{O}(m\log m) 个。原问题相当于平面内，\operatorname{O}(m\log m) 个点，分别查询 \operatorname{O}(n\log n) 个矩形内是否存在一个点并需要找出任意一个点。

:::warning[麻烦解法] 判定是否存在是经典的，可以离线后按照其中一个维度排序，利用扫描线的技巧处理。但由于该做法是基于判定问题等价于数量查询问题，而数量查询问题可差分成若干个左端点为 1 的矩形问题想加减。但如果要构造方案就必须要整体处理，因此可能需要将值域从 \operatorname{O}(m) 扩大到 \operatorname{O}(m\log m)，对 (b,y_1) 数对做离散化（这样就不至于只知道一维内有几个可以的而另外一维是谁不知道了），并做线段树前缀和即主席树，在查询时差出对应区间内线段树并做线段树上二分找出一组可行解。问题是有人这么写吗？这能写出来吗？ :::

显然没有人想写主席树上二分，所以观察性质。会发现第二个条件与 b 无关，两端点分别随 x_1 取值的增加单调递减，于是可以用双指针，以均摊 \operatorname{O}(m) 的代价推动 y_1 的 [\min,\max] 区间移动（利用莫队的思想可视作 \operatorname{O}(m) 次加入与删除，且每个 1\leq i\leq m 都出现 \operatorname{O}(1) 次）。如果我们能在此过程中实时维护合法的 b 显然问题就可以得以解决。

这是容易的，每次加入或删除一个 y_1 时，只会影响到它的因数 b。则开一个 map<int, int> all_b，\operatorname{all_b}(b_0) 表示在当前区间内的所有 y_1，b 作为因数被统计过多少次。实现插入删除是不困难的。总共均摊目前是 \operatorname{O}(m\log^2 m)，两个 \log 分别是调和级数和 map 的代价。

之后就简单了，在每个 x_1 的时刻枚举 a|x_1，用 all_b.lower_bound() 操作查询在 [a+1,\lfloor\frac{n}{X}\rfloor] 内是否有合法的 b，如果有，就通过它还原出一个 k\cdot b=y_1\in[\min,\max]，其中 [\min,\max] 是当前合法的 y_1 对应的区间，以此构造即可。

总复杂度为 \operatorname{O}(n\log^2n)，令 \operatorname{O}(n)=\operatorname{O}(m)。

:::success[AC code]

#include <bits/stdc++.h>

using namespace std;

constexpr int N = 2e5;
constexpr int M = 2e5;

int n, m;
vector<int> vec[max(N, M) + 1];
long long l, r;
map<int, int> all_b;

inline void add(int y_1) {
    if (1 <= y_1 && y_1 <= m) {
        for (int b : vec[y_1])
            all_b[b]++;
    }
}

inline void sub(int y_1) {
    if (1 <= y_1 && y_1 <= m) {
        for (int b : vec[y_1])
            if (!--all_b[b])
                all_b.erase(b);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // freopen("test.out", "w", stdout);
    cin >> n >> m >> l >> r;
    for (int i = 1; i <= max(n, m); i++)
        for (int j = i; j <= max(n, m); j += i)
            vec[j].push_back(i);
    all_b.emplace(INT_MAX, 114514);
    int min_y_1 = m + 1, max_y_1 = m;
    for (int x_1 = 1; x_1 <= n; x_1++) {
        int new_min_y_1 = max(1LL, min((l + x_1 - 1) / x_1, m + 1LL));
        int new_max_y_1 = min(r / x_1, m + 0LL);
        // cerr << min_y_1 << ' ' << max_y_1 << " -> ";
        // cerr << new_min_y_1 << ' ' << new_max_y_1 << '\n';
        while (min_y_1 > new_min_y_1)
            add(--min_y_1);
        while (max_y_1 < new_max_y_1)
            add(++max_y_1);
        while (min_y_1 < new_min_y_1)
            sub(min_y_1++);
        while (max_y_1 > new_max_y_1)
            sub(max_y_1--);
        // cerr << "go ok\n";
        array<int, 4> ans = array<int, 4>{-1, -1, -1, -1};
        for (int a : vec[x_1]) {
            int X = x_1 / a;
            long long min_b = a + 1, max_b = n / X;
            auto it = all_b.lower_bound(min_b);
            if (it -> first <= max_b) {
                auto b = it -> first;
                int y_1 = max_y_1 / b * b;
                int Y = y_1 / b;
                int x_2 = X * b, y_2 = Y * a;
                ans = array<int, 4>{x_1, y_1, x_2, y_2};
                break;
            }
        }
        if (ans[0] == -1)
            cout << -1 << '\n';
        else
            cout << ans[0] << ' ' << ans[1] << ' ' << ans[2] << ' ' << ans[3] << '\n';
    }
    return 0;
}

:::