Hexadecimal numbers

3

66 votes
Algorithms, Brute Force, C++, Searching
Problem

You are given a range \([L,\ R]\). You are required to find the number of integers \(X\) in the range such that \(GCD(X,F(X)) > 1\) where \(F(X)\) is equal to the sum of digits of \(X\) in its hexadecimal (or base 16) representation.

For example, \(F(27) = 1 + B = 1 + 11 = 12\) (\(27\) in hexadecimal is written as \(1B\)). You are aksed \(T\) such questions. 

Input format

  • The first line contains a positive integer \(T\) denoting the number of questions that you are asked.
  • Each of the next \(T\) lines contain two integers \(L\) and \(R\) denoting the range of questions.

Output Format

For each test case, you are required to print exactly \(T\) numbers as the output. 

Constraints

\(1 \leq T \leq \mathbb{50}\\ 1 \leq L,\ R \leq \mathbb{10^5}\)

Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

For the first test-case, numbers which satisfy the criteria specified are : 2,3. Hence, the answer is 2.

For the second test-case, numbers which satisfy the criteria specified are : 5,6,7 and 8. Hence the answer is 4.

For the third test-case, numbers which satisfy the criteria specified are : 7,8,9,10,11 and 12. Hence the answer is 6.

Editor Image

?