Unofficial editorial for GCDSET

editorial
, ,
1

Given L , R , G find the total elements in a set of range [L , R ] such that
The greatest positive integer which divides each element of the set is exactly G.

now simply the total elements would be (R / G) - (L-1) /G.

But there will be a case of a single element in set ie., if there is an only single element in the range then the value of G would be equal to that element.

For Ex ; L =4 , R =5 and G=2
the set in the range which divided by 2 is {4} only but no this is wrong, as the question says the The greatest positive integer which divides each element of the set is exactly G. so here for single element the greatest element which divides it is itself which is not equal to given G so the output would be 0.

So if the count of the element is 1 and G < L then answer will be 0
If u like this , my first editorial post please like and share.
Check Solution: CodeChef: Practical coding for everyone

10 Likes
3

I have tried even the same code as of you in python 3
But I am unable to get the AC

T=int(input())
while(T):

l,r,g=map(int,input().split())
count=0

count=int(r/g)-int((l-1)/g)


if(count==1 and g<l):
    print('0')
else:
     print(count)
T-=1
4

Can any give me a test case where my code goes wrong:

tt=int(input())
while tt>0:
    tt-=1
    total=0
    n=list(map(int,input().split()))
    for i in range(1,n[2]+1):
        if n[2]*i in range(n[0],n[1]+1):
            #print(n[2]*i)
            total+=1
    print(total)
5

instead of float division u should use int division
Here u go : -

count=r//g - (l-1)//g

check : CodeChef: Practical coding for everyone

1 Like
6

your code fails if count = 1 and G < L
For ex : L =4 , R =5 and G=2
Your code give 1 but output should be 0

1 Like
7

Thanks @ssrivastava990

8

WELCOME :slight_smile: