 # SELPEN - Editorial

Contest

Author: Rutuja Deshmukh
Tester: Vallabh Deshpande
Editorialist: Vallabh Deshpande

EASY-MEDIUM

Math

# PROBLEM:

Given integers A, B, R1, R2, R3, R4 count the number of integer pairs (P, Q) such that \frac{P}{Q} = \frac{A}{B} , R1 \leq P \leq R2 and R3 \leq Q \leq R4.

# QUICK EXPLANATION:

Reduce the fraction \frac{A}{B} to its simplest form by dividing both the numerator and denominator by their GCD. Let’s denote \frac{A}{GCD(A,B)} by X and \frac{B}{GCD(A,B)} by Y. The problem reduces to finding number of integers n such that R1 \leq X*n \leq R2 and R3 \leq Y*n \leq R4.

# EXPLANATION:

We need to find integer pairs (P, Q) such that \frac{P}{Q} = \frac{A}{B} , R1 \leq P \leq R2 and R3 \leq Q \leq R4. In order to find such pairs, we must first reduce \frac{A}{B} to its simplest form, otherwise we will undercount some pairs. This can be done by dividing both the numerator and denominator by their GCD. Let’s denote \frac{A}{GCD(A,B)} by X and \frac{B}{GCD(A,B)} by Y. The problem reduces to finding number of integers n such that R1 \leq X*n \leq R2 and R3 \leq Y*n \leq R4.

30 points solution:
Now that we have reduced the problem to find the number of valid n, we can just iterate on the possible values of n and check if it satisfies the given conditions. It can be done as follows:

Editorialist's Solution
#include<bits/stdc++.h>

using namespace std;

#define int long long
//O(n) Testing
void solve(){
int a, b, r;
cin>>a>>b>>r>>r>>r>>r;
int g = __gcd(a, b);
a /= g;
b /= g;
int ans = 0;
for(int i = ((r + a - 1)/a); i <= r/a; ++i){
int k = b*i;
if(k >= r && k <= r)
++ans;
}
cout<<ans<<"\n";
}

signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//oJudge();

int t = 1;
cin>>t;
while(t--){
solve();
}
return 0;
}


100 points solution:
The above solution takes Linear time, hence won’t pass all the test cases. The GCD function will take O(log(n)) time anyway, so we must look for a solution that is at most O(log(n)).

We know that to find n such that 0 \leq X*n \leq R2 we can calculate it as \lfloor \frac{R2}{X} \rfloor, therefore to find n such that R1 \leq X*n \leq R2, we can subtract all n following, 0 \leq X*n \leq (R1-1) from 0 \leq X*n \leq R2.

Since we have 2 inequalities, we just need to find the common values of n that satisfy both the inequalities. Therefore, we need to subtract
\lfloor max(\frac{(R1-1)}{X}, \frac{(R3-1)}{Y}) \rfloor from \lfloor min(\frac{R2}{X}, \frac{R4}{Y}) \rfloor.

The only exception is when both the ranges are disjoint. When that happens, the answer must be 0 but the difference \lfloor min(\frac{R2}{X}, \frac{R4}{Y}) \rfloor - \lfloor max(\frac{(R1-1)}{X}, \frac{(R3-1)}{Y}) \rfloor is less than 0, therefore we can take, max(\lfloor min(\frac{R2}{X}, \frac{R4}{Y}) \rfloor - \lfloor max(\frac{(R1-1)}{X}, \frac{(R3-1)}{Y}) \rfloor, 0).

Time Complexity: O(log(n)) per test case, (due to the GCD function).

(See the editorialist’s solution below for code).

# SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll gcd(ll a, ll b){
if(b==0) return a;
return gcd(b,a%b);
}
int main()
{
ll t;
cin>>t;

while(t--)
{

ll a,b,r1,r2,r3,r4;
cin>>a>>b>>r1>>r2>>r3>>r4;
ll gcdno= gcd(a,b);
a/=gcdno;
b/=gcdno;
//cout<<a<<" "<<b<<" ";//<<r1<<" "<<r2<<" "<<r3<<" "<<r4<<" "<<"\n";
if(a>r2 or b>r4) cout<<0<<"\n";
else{
if(r1%a==0) r1/=a;
else r1=r1/a + 1;
if(r3%b==0) r3/=b;
else r3=r3/b + 1;

r1 = r1>r3 ? r1: r3;
r2 = (r2/a)<(r4/b) ? (r2/a): (r4/b);
//cout<<r1<<" "<<r2<<"\n";
if(r2-r1+1 >=0)
cout<<r2-r1+1<<"\n";
else cout<<0<<"\n";
}
}

return 0;

}

Tester's Solution / Editorialist's Solution
#include<bits/stdc++.h>

using namespace std;

#define int long long
void solve(){
int a, b, r;
cin>>a>>b>>r>>r>>r>>r;
int g = __gcd(a, b);
a /= g;
b /= g;
int sub = max((r - 1)/a, (r - 1)/b), add = min(r/a, r/b);
}

signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//oJudge();

int t = 1;
cin>>t;
while(t--){
solve();
}
return 0;
}

2 Likes