 # GCDSET - EDITORIAL

Practice

Contest: Division 1

Contest: Division 2

Setter: Pritom Kundu

Tester: Teja Vardhan Reddy

Editorialist: Teja Vardhan Reddy

Easy

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

// 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. 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.

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

int main() {
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 .

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

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

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
{
int t=Integer.parseInt(st.nextToken());
StringBuilder sb =new StringBuilder();
int m=1000000007;
while(t--!=0)
{
long l=Long.parseLong(s);
long r=Long.parseLong(s);
long g=Long.parseLong(s);
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;
``````

}

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