Ragu has given a range (L, R] to Smith. Smith wants to require to find the number of integers ‘X’ in the range such that (Greatest common divisor) GCD(X, F(X)) > 1 where F(x) is equal to the sum of digits of ‘X’ in its hexadecimal (or base 16) representation.
Example: F(27) = 1+B=1+11=12 (27 in hexadecimal is written as 1B)
Constraints:
1 <= T <= 50
1 <= L
R <= 10^5
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:
Print the output in a separate lines exactly ‘T’ numbers as the output.
#include<bits/stdc++.h>
using namespace std;
int F(int x) //hexadeciaml
{
int sum = 0;
while(x > 0)
{
sum += x%16;
x = x/16;
}
return sum;
}
int search(int a, int b)
{
int count=0;
for(int i=a;i<=b;i++)
{
if(__gcd(i,F(i))>1)
count++;
}
return count;
}
int main()
{
int t,l,r;
cout<<"Enter the T number: ";
cin>>t;
while(t--)
{ cout<<"Enter range L and R : ";
cin>>l>>r;
int count=search(l,r);
cout<<"Number of integers: "<<count<<endl;
}
}Output_1:
Enter the T number: 2
Enter range L and R : 100 200
Number of integers: 62
Enter range L and R : 50 70
Number of integers: 13
Output_2:
Enter the T number: 2
Enter range L and R : 1000 1500
Number of integers: 309
Enter range L and R : 3500 6000
Number of integers: 1547
Output_3:
Enter the T number: 1
Enter range L and R : 1000 20000
Number of integers: 11854
Output_4:
Enter the T number: 1
Enter range L and R : 1000 100000
Number of integers: 61817
Output_5:
Enter the T number: 3
Enter range L and R : 500 800
Number of integers: 189
Enter range L and R : 5000 15000
Number of integers: 6230
Enter range L and R : 2300 6000
Number of integers: 2303
ScrShot
