GCDSET - EDITORIAL

PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Setter: Pritom Kundu

Tester: Teja Vardhan Reddy

Editorialist: Teja Vardhan Reddy

DIFFICULTY:

Easy

PREREQUISITES:

Basic Math

PROBLEM:

Find the size of largest set which is subset of \{l,l+1,...r-1,r\} such that largest positive integer that divides each of the element is exactly g.

EXPLANATION

  • Since each of the element must be divisible by g, we can shift our focus to only mutliples of g in the set.

Case 1: If there are more than one multiple of g in range [l,r].

  • Then we can see that there exist two numbers x and x+g which are multiples of g (we can obtain such pair by taking x as the smallest multiple of g in [l,r] since our assumption above guarantees x+g to be in [l,r]). We can rewrite them as k*g and k*g+g (= (k+1)*g).

  • Largest positive integer that divides k and k+1 is 1(Proof). Hence, largest positive integer that divides k*g and (k+1)*g is g.

  • Now largest possible set we can take is set of all multiples of g in [l,r]. Using above facts, we will prove that the largest integer that divides this set is g. We can see g divides all the numbers in this set. And assume that p \gt g divides all the elements in the set which mean p divides both k*g and (k+1)*g which is false as we proved above g is the largest positive integer that divides k*g and (k+1)*g.

  • So now, we need to count the number of multiples of g in [l,r] (lets denote by m(l,r)). We can see m(l,r) = m(0,r) - m(0,l-1). Now m(0,x) = floor(x/g) + 1 (considering 0 is a multiple of g).

Case 2: If there is one multiple of g in [l,r].

  • Let that multiple be x, Now we have only two possibilities either \{ \} or \{x\}. Largest integer that divides elements of {x} is x. Hence x must be equal to g for answer to be 1 otherwise answer is 0.

Case 3: If there is no multiple of g in [l,r]. Here, answer is 0.

TIME COMPLEXITY

O(1) per test case.

SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>
#define LL long long
using namespace std;
 
int main ()
{
    int t;
    cin>>t;
    while (t--) {
        LL l, r, g;
        cin>>l>>r>>g;
 
        LL d = r/g - (l-1)/g;
        if (d!=1)   cout<<d<<endl;
        else {
            if (l<=g && g<=r)   cout<<1<<endl;
            else                cout<<0<<endl;
        }
    }
}
Tester's Solution
//teja349
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
//setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val
 
using namespace std;
using namespace __gnu_pbds;
 
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define flush fflush(stdout) 
#define primeDEN 727999983
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
// find_by_order()  // order_of_key
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
 
#define int ll
main(){
    std::ios::sync_with_stdio(false); cin.tie(NULL);
    int t;
    cin>>t;
    while(t--){
        int l,r,g;
        cin>>l>>r>>g;
        l--;
        int cnt1,cnt2;
        cnt1=l/g;
        cnt2=r/g;
        if(cnt2-cnt1>=2){
            cout<<cnt2-cnt1<<endl;
        }
        else if(cnt2==1 && cnt1==0){
            cout<<1<<endl;
        }
        else{
            cout<<0<<endl;
        }
    }
    return 0;   
}

Feel free to Share your approach, If it differs. Suggestions are always welcomed. :slight_smile:

8 Likes

Hi. I tried this method, but I am unable to find the error.
I tried cases like:
4 4 4
4 5 1
1 1 1
3 3 4
5 8 3
9 10 5
I get the right answers for these, but the final submission is wrong.
Can you please help me with this?

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

int main() {
	// your code goes here
	int t;
	cin >> t;
	while(t--)
	{
	    unsigned long long l,r,g;
	    cin >> l >> r >> g;
	    
	    if(l%g==0)
	        cout << r/g - l/g + 1;
        else
            cout << r/g - l/g;
        cout << "\n";
	}
	return 0;
}
1 Like

You didn’t factor in the case of only one multiple of g . In case g is less than l , the output should be 0.

Ohhh. Thanks a lot. Sorry for being naive there.
Now I found that if there is only 1 element (multiple), then that should be g, and if not, then the answer should be 0.

Thanks again :grin:.

1 Like

Can someone help me, where am I wrong?

void solve(){
int t; //no. of testcases 
cin>>t;
while(t--){
	int l,r,g;
	cin>>l>>r>>g; // left,right,gcd
	int x = ceil(l*1.0/g); // g*x is least number above l divisible by g
	// int y = g*x;
	int z = g*(x+1); // if g*(x+1) <=r (is present in range) then gcd(g*x,g*(x+1))= g so ans !=0 

	if(z<=r || x==1){ // x=1 added so that l<=g<=r<2g is covered although for x=1 and l<=r<g   condn is true but r/g(0)-ceil(l/g)(1) +1 = 0 
		int y1 = r/g;
		cout<<y1-x+1<<"\n";

	}
	else{
		cout<<0<<"\n";
	}
}}

Ok got it, it’s due to double and long double
while finding ceil(l*1.0/g), l*1.0 returns as a double which should be returned as long double instead,
so direct casting ceil((long double)l/g) gave the correct answer.
[Sorry for the lame error]

1 Like

Video Link : https://youtu.be/jB3YIdAwqeo

1 Like

that corner case ,when there was one multiple of g literally cost my rating ,nice question

could some help me with my code where it is failing
t=int(input())
for _ in range(t):
l,r,g=map(int,input().split())
c=0
s=1
for i in range(l,r+1,s):
if i%g==0:
c+=1
s=g
print©

Didn’t find anything wrong with this
pls help as the final submission is wrong

   import java.util.*;
import java.io.*;
class Contest{
    public static void main(String args[]) throws IOException
    {
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st =new StringTokenizer(br.readLine());
        int t=Integer.parseInt(st.nextToken());
        StringBuilder sb =new StringBuilder();
        int m=1000000007;
        while(t--!=0)
        {
            String s[]=br.readLine().split(" ");
            long l=Long.parseLong(s[0]);
            long r=Long.parseLong(s[1]);
            long g=Long.parseLong(s[2]);
            long left=(long)Math.ceil(((double)l)/g);
            long right=(long)Math.floor(((double)r)/g);
            if(left>right)
            {
                sb.append("0").append("\n");
            }
            else
            {
                long temp=right-left+1;
                if((temp==1 && (g<l || g>r)) || g<1)
                {
                    sb.append("0").append("\n");
                }
                else
                sb.append(temp).append("\n");
            }
        }
        System.out.println(sb);
    }
}

My logic still ends up as WA (wrong answer). I’m unable to find a case where my logic breaks. Can anyone help me with a case ?

LOGIC : Given l, r and g. Find the first number which is divisible by g in [l,r] and name it as start and find the last number which is divisible by g in [l,r] and name it as end. if start > r or end < l then answer is 0 else answer is (((end-start)/g)+1)

    public void solve(InputReader input, OutputWriter output)
            throws IOException {
        int cases = input.nextInt();
        while ((cases--)>0) {
            long l = input.nextLong();
            long r = input.nextLong();
            long g = input.nextLong();
            long start = l + (l%g==0?0:g-(l%g));
            long end = r - (r%g);
            if (start>r || end<l) {
                output.printLine(0);
            } else {
                output.printLine(((end-start)/g)+1);
            }
            output.flush();
        }
    }
1 Like

edit : found out the case

It took a while to hit me hard from the problem statement. Hope this explanation will be of help to someone.

Say case 14 18 7 answer should be 0 and not 1 since there is only one number in the given range which is divisible by 7 which is 14 but {14} is not a nice set since according to the rules of the nice set the largest number which divides all the element in the nice set should be exactly g which here is 7 but now the largest number which divides all the elements in the set would be 14 hence this set is not a nice set. So the answer is 0.

2 Likes

#include <bits/stdc++.h>
typedef unsigned long long int ll;
using namespace std;

int main() {
ll t;
cin>>t;

ll l,r,g;
while(t–){
cin>>l>>r>>g;

   ll q=ceil((double)l/g),q1;
   
   q1=r/g;
   
  if(g==1)cout<<q1-q+1<<endl;
  else if(q==q1 && q*g!=g)cout<<"0\n";
  
  else if((r/g)-(l/g)==1 && q!=1)cout<<"0\n";
  
  else if(q1*g<=r && q1*g>=l && q*g<=r && q*g>=l) 
          cout<<q1-q+1<<endl;
   
   else cout<<"0\n";  

}
}
please tell which case am i missing?

Hi coders,
I’ve used the A.P approach to answer the question. I calculated the first and last term divisible by g and then calculated the no. of terms. Can u tell me what’s wrong with my code, i’m getting wrong answer.

#include
#define ll long long int
using namespace std;

int main()
{
ll t;
cin>>t;

while (t--)
{
    ll l,r,g;
    cin>>l>>r>>g;
    ll p,ans,n1,n2;
    
    if (r<g)
     ans=0;
     
    else 
    {
      p=l/g;
      if (p==0)
      n1=g;
      else 
      n1=l+g-(l%g);
      
      if (n1>r)
        ans=0;
      else 
      {
          p=r/g;
          if (p==0)
           n2=r;
          else 
          n2=r-(r%g);
          
          if ((n2-n1)>=0)
          ans=((n2-n1)/g)+1;
          else 
          ans=0;
       }
      
    }

    cout<<ans<<endl;    
}
return 0;

}

please check my code…
i’m getting wrong answer.

https://www.codechef.com/viewsolution/30411031

HEY what i thought is tht let the no in between l and r be a prime multiple of g

means all no like
g1
g
2
g3
g
5
g7
g
11
g*13
and so o which comes under the category of l and r is the answer since they dont have multiples greater than g…

https://www.codechef.com/viewsolution/36029354

plz… tell me which case i am leaving