PROBLEM LINK:
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,...r1,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,l1). 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  (l1)/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(cnt2cnt1>=2){
cout<<cnt2cnt1<<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.