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 3.00
C++ 3.00
C++14 3.00
C# 5.00
Go 5.00
Java 5.00
JavaScript 5.00
Objective-C 5.00
Perl 5.00
PHP 5.00
Python 5.00
Python3 5.00
Ruby 5.00
VB.Net 5.00

Problem Stats

46/150

Solve/Submission

Ranking

# User Language Timing
01 feodorv Cpp 0.06s
02 Morass Cpp14 0.16s
03 ssavi Cpp14 0.96s
04 seyedssz Cpp14 1.24s
05 jalal Cpp14 1.25s
06 atik Cpp 1.31s
07 kpretomazi Cpp 1.32s
08 rashedul007 Cpp 1.33s
09 bengal_tiger Cpp 1.35s
10 rajdipsaha Cpp 1.36s
11 haasib Cpp14 1.41s
12 sadia2427 Cpp14 1.41s
13 subhashis_cse Cpp14 1.47s
14 KNUTH Cpp14 1.47s
15 anowar1112 Cpp14 1.47s
16 tariqiitju Cpp14 1.47s
17 smriad Cpp14 1.48s
18 ahqmrf Cpp14 1.49s
19 ammasum Cpp14 1.49s
20 prantacse14 Cpp14 1.50s
21 hmtanbir Cpp14 1.50s
22 ProKawsar Cpp14 1.56s
23 emrul Cpp14 1.56s
24 AlaminJust Cpp14 1.57s
25 bishal_biswas Cpp14 1.59s
26 lightlessShadO Cpp14 1.60s
27 umli Cpp14 1.67s
28 Ishrak Cpp14 1.69s
29 dmehrab06 Cpp14 1.72s
30 sazal_dev Cpp14 2.79s
Feedback

Your feedback is our precious!



Or call +88 02 9853138 for support