1 条题解
-
0
题目分析
30 pts
枚举两个数并判断,
60 pts
根据 的性质, 等价于
那么有 $\operatorname{gcd}(a, b) = \operatorname{gcd}(a, a \operatorname{xor} c) = c$
而其中 是 的约数,因此我们可以枚举 ,再枚举 ,由于 $\frac{n}{1} + \frac{n}{2} + \frac{n}{3} + \ldots + \frac{n}{n} = O(n \log n)$,再算上 的一只 ,总复杂度
100 pts
因为 是肯定无解,所以不妨设
那么有 $\operatorname{gcd}(a,b) \le a - b, a \operatorname{xor} b \ge a - b$,很明显有 。那么我们在 60 pts 的算法基础上,有 ,所以我们只需判断 即可,复杂度
- 1
信息
- ID
- 94
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 3
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者