Header Ads Widget

Hexadecimal numbers

 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

1T501L, R105

Sample Input
3
1 3
5 8
7 12
Sample Output
2
4
6
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.

Code:-

#include<bits/stdc++.h>
using namespace std;

// function for calculate gcd
int gcd(int a,int b)
{
    int n=a>b?b:a;
    for(int i=n;i>1;i--)
    {
        if(a%i==0 && b%i==0)
         return 0;
    }
    return 1;
}

//Driver function
int main()
{
    int t,l,r;
    cin>>t;
    while(t--)
    {
        cin>>l>>r;
        int ans=0;
        for(int i=l;i<=r;i++)
        {
            int x=i;
            int sum=0;
            // lopgic for calculate Hexadecimal number
            while(x!=0)
            {
                int r=x%16;
                x=x/16;
                sum=sum+r;
            }
            int f=gcd(i,sum);
            // if gcd greater than 1 than return 0
            if(f==0)
             ans++;
        }
        cout<<ans<<endl;
    }
}