TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P2782
  • 题目
  • P2782最大奇因子
    限制 : 时间限制 : 4000 MS   空间限制 : 565536 KB
    问题描述

    f(x)表示x的最大奇因子,比如x=6时f(x)=3,x=7时f(x)=7
    给出一个n,接下来n行每一行给出一个l和r(其中l<=r),求f(l)+f(l+1)+f(l+2)+……+f(r-1)+f(r)

    输入格式

    输入第1行,包含一个整数n
    接下来n行,每一行包含2个整数l和r(其中l<=r)

    输出格式

    输出n行,每行一个整数表示f(l)+f(l+1)+f(l+2)+……+f(r-1)+f(r)

    样例输入

    样例输入1:
    3
    1 5
    6 12
    1 12

    样例输入2:
    4
    1 7
    8 19
    20 20
    1 20

    样例输出

    样例输出1:
    11
    39
    50

    样例输出2:
    21
    110
    5
    136

    提示

    【数据范围】
    对于第一组数据,对于所有l,r,1<=l<=r<=1000,n<=1000;
    对于第二组数据,对于所有l,r,1<=l<=r<=1000000,n<=1000000。

    【背景】
    这是数学老师上课出的题目,是要求f(1)+……+f(2^k) k∈R,数学数组累和更简便
    然后我和室长说,,室长说用lowbit只需要n,然后我就想到了坑他的办法


    来源  感谢UncleGai命题,ShadowIterator被黑,nodgd放题