#H26. 【拓展题】晶体分裂
【拓展题】晶体分裂
Background
你受命前往一颗遥远的行星,完成一项极其重要的任务。这颗行星的核心储存着古老的能量晶体,这些能量晶体拥有神秘的自我分裂特性。为了通过这一考验,你需要分裂这些能量晶体,将它们变成能量稳定的形式。
Description
最初,这颗能量晶体的能量数值为 m
。你可以在每次操作中选择能量值大于 1
的晶体,将其分裂为三个较小的能量晶体,例如现有晶体能量为 ,分解为三个小晶体:$\lfloor x/2 \rfloor,\ x \mod 2,\ \lfloor x/2 \rfloor$。分裂的过程会持续,直到所有晶体的能量都稳定为 0
或 1
。
在完成所有分裂后,你需要在一定范围内(从第 k
个到第 s
个位置)观察这些能量晶体的状态,确定其中有多少晶体的能量值为 1
。只有正确回答这个问题,你才能完成任务,安全返回母舰。
Format
Input
第一行包含三个整数 $(0 \leq m \leq 10^{14}, 0 \leq s - k \leq 10^5, 1 \leq k, s)$,表示初始能量数值与查询范围。
输入保证 合法,下标从 1
开始。
Output
一个整数,表示给定范围内 1
的总数。
Samples
7 1 4
4
77186498974 15392062479 15392086306
13383
Related
In following homework: