2083: I 孤独一生2

内存限制:128 MB 时间限制:3 S
题面:传统 评测方式:文本比较 上传者:
提交:1 通过:1

题目描述

火星之上的住民是使用4进制的,因为他们的手指很少。火星上面的单身小伙小姑娘们都很讨厌5这个数,因为这个数在4进制下的表示是11

 

给定一个区间[L,R],计算这个区间内有多少数x,使得x4进制下的表示不包含任何5的正倍数,0不计算在内,比如4进制下101这个数不包含11的倍数。

Hint:就是一个数x,转换成4进制之后,其子串中不包含11,22,33,110,121,132……,因为这些是4进制下11的倍数,比如4进制下112由于包含11因此这个数不算,但是10,100,1000是允许的,1001不允许是因为1001本身是4进制下11的倍数。

输入格式

多组数据,每组数据2个正整数L,R保证1<=L<=R<=10^9(L,R都以10进制给出)

输出格式

输出区间内这样的数的个数。

输入样例 复制

1 10
1 20

输出样例 复制

8
16

数据范围与提示

第二组样例中,11,22,33,110包含了11的倍数