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