跳转至

算法笔记

BISHI27 构造数对

w3903771/algorithm

BISHI27　构造数对¶

简单通过率 51.66%python3样例通过牛客 AC

牛客原题　源码

讲解章节：构造

一句话

找 (a,b) 满足 1<=a,b<=x、b|a、a*b>x、a/b<x。

解题思路¶

这题考什么¶

看似构造，实则 x <= 100，直接 O(x^2) 暴力枚举全部数对即可（最多 1e4 次判断），根本不需要动脑推公式。数据规模决定做法的典型例子。

顺带说一句规律：除了 x = 1 之外都有解。取 a = b = x 时

b | a 成立；
a*b = x^2 > x 当且仅当 x > 1；
a/b = 1 < x 当且仅当 x > 1。

所以 x >= 2 时 (x, x) 恒为一组合法解，x = 1 时无解输出 -1。代码里仍然写暴力，既是对上面推论的自检，也避免推错。

数据规模与复杂度¶

x <= 100，O(x^2) = 1e4，瞬间出结果。

坑在哪¶

条件 4 是严格小于：a/b < x，注意 a=b 时比值为 1，x=1 时 1<1 不成立；
条件 3 是严格大于 x，不是 >=；
a/b 用整除判断即可（已保证 b|a），别写浮点比较；
答案不唯一：符合四条约束的数对往往有很多组，题面也明说可以输出任意一组。本解法按「b 从小到大、a 取 b 的倍数从小到大」的顺序枚举，输出第一个命中的，所以 x = 10 时给出的是 "6 2" 而不是样例里的 "6 3"，两者都合法。这类题本地要用 special judge（特殊评测程序，按题目条件验证选手输出是否合法，而不是与标准答案逐字符比对）：本题配了 solutions/_spj/BISHI27.py，它逐条复查四个条件，并在输出 -1 时暴力确认确实无解。

参考实现¶

solutions/BISHI27.py
import sys


def main() -> None:
    x = int(sys.stdin.buffer.read().split()[0])
    for b in range(1, x + 1):
        for a in range(b, x + 1, b):        # 直接按 b 的倍数枚举 a，保证 b | a
            if a * b > x and a // b < x:
                print(a, b)
                return
    print(-1)


main()