SELPEN - Editorial

editorial
, ,
1

PROBLEM LINK:

Contest

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

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

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[4];
    cin>>a>>b>>r[0]>>r[1]>>r[2]>>r[3];
    int g = __gcd(a, b);
    a /= g;
    b /= g;
    int ans = 0;
    for(int i = ((r[0] + a - 1)/a); i <= r[1]/a; ++i){
        int k = b*i;
        if(k >= r[2] && k <= r[3])
            ++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[4];
    cin>>a>>b>>r[0]>>r[1]>>r[2]>>r[3];
    int g = __gcd(a, b);
    a /= g;
    b /= g;
    int sub = max((r[0] - 1)/a, (r[2] - 1)/b), add = min(r[1]/a, r[3]/b);
    cout<<max(add - sub, 0LL)<<"\n";
}

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

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