DCP-16: Mr. And Mrs. A Back to All Problems

Medium Search Techniques > Binary Search/Bisection


This is the story of Mr. and Mrs. A. They always love to play with integers. One day Mr. A asks Mrs. A to find any three integers X, Y, Z such that X = Y^Z (X, Y, Z>1). Mrs. A answers the question within 1 second. Mr. A wants to make the task harder for Mrs. A so Mr. A gives two more integers L, R. Now Mr. A asks find how many integers X, are present from L to R. Mrs. A never likes to loss to Mr. A. So Mrs. A seeks help from you. Can you do it for Mrs. A? Input: ------ First line gives an integer T (<=10^5), number of integers. Each line contains two integers L, R (1<=L<=R<=10^12) Output: ------- For every case, print case number and require answer. Look at sample output. Sample Input ------------ 2 4 9 10 20 Sample Output ------------- Case 1: 3 Case 2: 1 **Sample Input/output Explanation:** From 4 – 9 there are 3 numbers - 4 = 2^2, 8 = 2^3, 9 = 3^2 From 10 – 20 there is only one number – 16 = 2^4. 16 can also express as 16 = 4^2. But count for only once.


Problem Setter:

Shakil Ahmed

Please login to submit solution to this problem.

Problem Limits

Language Time Limit (seconds)
C/C++ 3.00
Java 5.00
C# 5.00
PHP 5.00

Problem Stats

29/90

Solve/Submission

Ranking

# User Language Timing
01 seyedssz Cpp 1.24s
02 jalal Cpp 1.25s
03 haasib Cpp 1.41s
04 sadia2427 Cpp 1.41s
05 KNUTH Cpp 1.47s
06 subhashis_cse Cpp 1.47s
07 tariqiitju Cpp 1.47s
08 anowar1112 Cpp 1.47s
09 smriad Cpp 1.48s
10 ammasum Cpp 1.49s
11 ahqmrf Cpp 1.49s
12 prantacse14 Cpp 1.50s
13 hmtanbir Cpp 1.50s
14 emrul Cpp 1.56s
15 ProKawsar Cpp 1.56s
16 AlaminJust Cpp 1.57s
17 lightlessShadO Cpp 1.60s
18 umli Cpp 1.67s
19 Ishrak Cpp 1.69s
20 dmehrab06 Cpp 1.72s
21 sazal_dev Cpp 2.79s
Feedback

Your feedback is our precious!



Or call +88 02 9853138 for support