1 条题解

  • 0
    @ 2026-11-15 14:20:04

    题目分析

    30 pts

    枚举两个数并判断,O(n2log⁡n)O(n^2\log{n})

    60 pts

    根据 xorxor 的性质,axor⁡b=ca \operatorname{xor} b = c 等价于 axor⁡c=ba \operatorname{xor} c = b

    那么有 $\operatorname{gcd}(a, b) = \operatorname{gcd}(a, a \operatorname{xor} c) = c$

    而其中 cc 是 aa 的约数,因此我们可以枚举 cc,再枚举 a=i×ca = i \times c,由于 $\frac{n}{1} + \frac{n}{2} + \frac{n}{3} + \ldots + \frac{n}{n} = O(n \log n)$,再算上 gcd⁡\operatorname{gcd} 的一只 log⁡\log,总复杂度 O(nlog⁡2n)O(n \log^2 n)

    100 pts

    因为 a=ba = b 是肯定无解,所以不妨设 a>ba > b

    那么有 $\operatorname{gcd}(a,b) \le a - b, a \operatorname{xor} b \ge a - b$,很明显有 c=a−bc = a - b。那么我们在 60 pts 的算法基础上,有 gcd⁡(a,a−c)=c\operatorname{gcd}(a, a - c) = c,所以我们只需判断 axor⁡c=a−ca \operatorname{xor} c = a - c即可,复杂度 O(nlog⁡n)O(n \log{n})

    • 1

    信息

    ID
    94
    时间
    1000ms
    内存
    256MiB
    难度
    3
    标签
    递交数
    1
    已通过
    1
    上传者