题目描述
根据算术基本定理,任何一个大于 1 的自然数都可以唯一地分解为若干个质数的乘积。
现在给定一个闭区间 [l,r],请你统计在这个区间内,有多少个整数满足以下条件:
- 在其质因数分解中,质因数 2 的指数恰好为 1;
- 在其质因数分解中,质因数 3 的指数恰好为 2。
换言之,如果将该数分解为 2p2×3p3×5p5…,则必须满足 p2=1 且 p3=2。
输入格式
输入仅包含一行,两个正整数 l 和 r —— 分别表示区间的左边界和右边界。
输出格式
输出一行,一个整数,表示在区间 [l,r] 内满足条件的数字个数。
样例输入 1
1 100
样例输出 1
2
样例输入 2
18 18
样例输出 2
1
说明
样例解释
- 在第一个样例中,区间 [1,100] 内共有 2 个满足条件的数字,分别是 18 和 90:
- 18=21×32 ;
- 90=21×32×51 ;
- 注意:虽然 36 也是 18 的倍数,但 36=22×32,其中 2 的指数为 2 而不是 1,所以不满足条件;同理 54=21×33,其中 3 的指数为 3 而不是 2,也不满足条件。
- 在第二个样例中,区间只包含数字 18,且它满足条件,因此输出 1。
数据范围
- 对于 30% 的数据,保证 1≤l≤r≤1000。
- 对于另外 20% 的数据,保证特殊性质:l=r。
- 对于 100% 的数据,保证 1≤l≤r≤100000。
- 保证所有的输入值均为整数。