4115. 区间内的兼容数字之和 II 🔒
难度困难
题目描述
给你两个整数 n 和 k。
如果一个 正 整数 x 同时满足以下两个条件,则称其为 兼容:
abs(n - x) <= k(n & x) == 0
返回所有 兼容 整数 x 的总和。
由于答案可能很大,请返回其对 109 + 7 取模后的结果。
注意:
- 这里,
&表示 按位与 运算符。 - 整数
i和j之间的 绝对 差定义为abs(i - j)。
示例 1:
输入: n = 2, k = 3
输出: 10
解释:
兼容整数为:
x = 1,因为abs(2 - 1) = 1且2 & 1 = 0。x = 4,因为abs(2 - 4) = 2且2 & 4 = 0。x = 5,因为abs(2 - 5) = 3且2 & 5 = 0。
因此,答案为 1 + 4 + 5 = 10。
示例 2:
输入: n = 5, k = 1
输出: 0
解释:
区间 [4, 6] 中没有兼容整数。因此,答案为 0。
提示:
1 <= n <= 10150 <= k <= 1015
解法
方法一
1 | |
1 | |
1 | |
1 | |