简答题
偏难
#17250
试题名称 :有趣的数字和 时间限制 :1.0 s 内存限制 :512.0 MB
试题名称:有趣的数字和
时间限制:1.0 s
内存限制:512.0 MB


答案与解析
正确答案:<pre class="brush:python;toolbar:false;">def cal2(n, p):
"""
计算奇偶性为p的 0~n 的有趣的数之和,要求n为2^k - 1的形式
:return: 有趣的数量, 有趣的数之和
"""
if n == 0:
return 1 - p, 0
if n == 1:
return 1, p
return (n + 1) // 2, n * (n + 1) // 4
def cal(n, p):
"""
计算奇偶性为p的 0~n 的有趣的数之和
:return: 有趣的数量, 有趣的数之和
"""
if n <= 1:
return cal2(n, p)
x = 1
while x * 2 <= n:
x *= 2
# 找出最大x=2^k,x-1=2^k-1 <= n
cntl, sl = cal2(x - 1, p)
# 剩下部分:最高位1去掉,剩余数位奇偶性相反 1-p
cntr, sr = cal(n - x, 1 - p)
# 总数 = 左半部分 + 右半部分
total_cnt = cntl + cntr
# 总和 = 左半和 + 右半和 + 高位x 乘右边数字个数
total_sum = sl + sr + x * cntr
return total_cnt, total_sum
# 主程序
l, r = map(int, input().split())
# 0 ~ l-1 的符合条件数字总和
_, ansl = cal(l - 1, 1)
# 0 ~ r 的符合条件数字总和
_, ansr = cal(r, 1)
# [l, r] 区间和 = 0~r总和 - 0~l-1总和
print(ansr - ansl)</pre>
这道题暂未补解析。