Ilumina 题解

30 分解法

$a, c \le 10$ 的部分分。

已知 $b = \left \lfloor \dfrac{a}{n} \right \rfloor$，$c = \left \lfloor \dfrac{b}{m} \right \rfloor$，并且 $a$ 和 $c$ 的值已经给定。我们将 $b = \left \lfloor \dfrac{a}{n} \right \rfloor$ 代入 $c = \left \lfloor \dfrac{b}{m} \right \rfloor$ 中，得到下列式子。

$$c = \left \lfloor \dfrac{\left \lfloor \dfrac{a}{n} \right \rfloor}{m} \right \rfloor $$

因为 $n, m, a, b, c$ 均为正整数，并且 $n$ 和 $m$ 在 $b = \left \lfloor \dfrac{a}{n} \right \rfloor$ 和 $c = \left \lfloor \dfrac{b}{m} \right \rfloor$ 中均为分母，因此只有当 $n \le a$ 且 $m \le b$ 时，$b$ 和 $c$ 才为正整数。

枚举 $[1, a]$ 中的整数 $n$ 和 $\left[1, \left \lfloor \dfrac{a}{n} \right \rfloor \right]$ 中的整数 $m$，并判断是否有满足 $\left \lfloor \dfrac{\left \lfloor \dfrac{a}{n} \right \rfloor}{m} \right \rfloor = c$ 的 $n$ 和 $m$ 即可。

---

60 分解法

$a, c \le 10^3$ 的部分分。

使用 $\{ x \}$ 表示 $x$ 的小数部分，显然 $\{ x \} <1$，因此下列式子中 $\left \{ \dfrac{a}{n} \right \}$ 的值不可能改变式子的取值。

$$\left \lfloor \dfrac{a}{nm} \right \rfloor = \left \lfloor \dfrac{\dfrac{a}{n}}{m} \right \rfloor = \left \lfloor \dfrac{\left \lfloor \dfrac{a}{n} \right \rfloor + \left \{ \dfrac{a}{n} \right \} }{m} \right \rfloor = \left \lfloor \dfrac{\left \lfloor \dfrac{a}{n} \right \rfloor}{m} \right \rfloor $$

所以 $c = \left \lfloor \dfrac{a}{nm} \right \rfloor$。因为 $n$ 和 $m$ 可以为任意正整数，我们令 $n = 1$，此时 $b = a$，$c = \left \lfloor \dfrac{a}{m} \right \rfloor$。枚举 $m$ 即可。

---

80 分解法

$a, c \le 10^3$ 和特殊性质的部分分。

对于特殊性质，因为合法的 $b$ 始终存在，可以发现有如下等式成立。

$$c = \left \lfloor \dfrac{\left \lfloor \dfrac{a}{n} \right \rfloor}{m} \right \rfloor = \left \lfloor \dfrac{b}{m} \right \rfloor $$

$m$ 可以为任意正整数，因此我们令 $m = 1$，即可得到 $b = c$。直接输出 $c$ 的值即可。

---

正解

由 60 分解法可以发现，问题转化成了判断是否存在正整数 $m$ 使得 $c = \left \lfloor \dfrac{a}{m} \right \rfloor$。

如果存在这样的 $m$，由于构造中 $n=1$，直接输出 $a$ 即可。

$$\left \lfloor \dfrac{a}{\left \lfloor \dfrac{a}{c} \right \rfloor} \right \rfloor \ge \left \lfloor \dfrac{a}{\dfrac{a}{c}} \right \rfloor = \left \lfloor c \right \rfloor = c = \left \lfloor \dfrac{a}{m} \right \rfloor $$

存在合法的 $m$ 当且仅当存在区间 $[l,r]$ 满足 $l \leq r$ 且对于 $i \in [l,r] \cap \mathbb{Z}$ 有 $\left \lfloor \dfrac{a}{i} \right \rfloor =c$。

很显然，最大的满足条件的 $i$（使用 $i_0$ 表示）满足 $i_0 \times c \leq a$ 且 $(i_0+1) \times c > a$，容易得到 $i_0 = \left \lfloor \dfrac{a}{c} \right \rfloor$，计算 $i_0$ 的值并且检验 $\left \lfloor \dfrac{a}{i_0} \right \rfloor$ 是否等于 $c$ 即可判断是否存在合法的 $m$。

单组数据时间复杂度 $O(1)$。

#include <iostream>
using namespace std;
using ll = long long;

int t;
ll a, c;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    for (cin >> t; t; --t) {
        cin >> a >> c;
        if (a < c) cout << "-1\n";
        else cout << (a / (a / c) == c ? a : -1) << '\n';
    } return 0;
}

可能的其他解法

由 60 分解法可以得到 $m$ 具有单调性，因此可以对 $m$ 进行二分查找。单组数据时间复杂度 $O(\log n)$。