DIF_GCD-Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Jeevan Jyot Singh
Testers: Jatin Garg, Tejas Pandey
Editorialist: Devendra Singh

DIFFICULTY:

1540

PREREQUISITES:

Greatest Common Divisor

PROBLEM:

Chef has two numbers N and M. He calls a pair of numbers (A, B) good if it satisfies the following conditions:

  • 1 \le A, B \le M
  • \gcd(A, B) \ge N

Chef wants to find a good pair (A, B) such that the value of |A - B| is maximized. Can you help Chef? (Here |X| represents the absolute value of X).

If there are multiple good pairs for which the value of |A - B| is maximized, you can print any of them. It can be proved that under the given constraints, at least one good pair always exists.

EXPLANATION:

WLOG, Let us assume A\leq B for the further discussion.
Observation 1: Let g\geq N be the GCD of A and B in the optimal answer then A=g as if A>g we can make A=g as it will further improve the answer and still satisfy the constraints of the problem. Similarly choose B=M-M%g the greatest multiple of g(\leq M) by same reasoning.
Observation 2: Let g\geq N be the GCD of A and B in the optimal answer. Then g<2\cdot N. If M<2\cdot N then there are no two distinct multiples of any number between N to M that are both less than M and the maximum possible answer is this case is 0. Now M\geq2\cdot N Suppose g\geq2\cdot N, Then the maximum possible answer with this value of g is M-2\cdot N (maximum value of B is M and minimum value of A is g). The minimum value if we choose A( or g) as N is (M-M%N)-N\leq M-2*N-1. Therefore g<2\cdot N

Thus from these observations we have the solution as: if M<2\cdot N the maximum value of |A - B| is zero hence print any number twice between N and M. Otherwise iterate on the value of g from N till 2\cdot N-1 choosing A as g and B as M-M%g and choose the values of A and B such that the value of |A - B| is maximized.

TIME COMPLEXITY:

O(N) for each test case.

SOLUTION:

Setter's solution
#ifdef WTSH
    #include <wtsh.h>
#else
    #include <bits/stdc++.h>
    using namespace std;
    #define dbg(...)
#endif

#define int long long
#define endl "\n"
#define sz(w) (int)(w.size())
using pii = pair<int, int>;

const long long INF = 1e18;

const int N = 1e6 + 5; 

// -------------------- Input Checker Start --------------------

long long readInt(long long l, long long r, char endd)
{
    long long x = 0;
    int cnt = 0, fi = -1;
    bool is_neg = false;
    while(true)
    {
        char g = getchar();
        if(g == '-')
        {
            assert(fi == -1);
            is_neg = true;
            continue;
        }
        if('0' <= g && g <= '9')
        {
            x *= 10;
            x += g - '0';
            if(cnt == 0)
                fi = g - '0';
            cnt++;
            assert(fi != 0 || cnt == 1);
            assert(fi != 0 || is_neg == false);
            assert(!(cnt > 19 || (cnt == 19 && fi > 1)));
        }
        else if(g == endd)
        {
            if(is_neg)
                x = -x;
            if(!(l <= x && x <= r))
            {
                cerr << l << ' ' << r << ' ' << x << '\n';
                assert(false);
            }
            return x;
        }
        else
        {
            assert(false);
        }
    }
}

string readString(int l, int r, char endd)
{
    string ret = "";
    int cnt = 0;
    while(true)
    {
        char g = getchar();
        assert(g != -1);
        if(g == endd)
            break;
        cnt++;
        ret += g;
    }
    assert(l <= cnt && cnt <= r);
    return ret;
}

long long readIntSp(long long l, long long r) { return readInt(l, r, ' '); }
long long readIntLn(long long l, long long r) { return readInt(l, r, '\n'); }
string readStringLn(int l, int r) { return readString(l, r, '\n'); }
string readStringSp(int l, int r) { return readString(l, r, ' '); }
void readEOF() { assert(getchar() == EOF); }

vector<int> readVectorInt(int n, long long l, long long r)
{
    vector<int> a(n);
    for(int i = 0; i < n - 1; i++)
        a[i] = readIntSp(l, r);
    a[n - 1] = readIntLn(l, r);
    return a;
}

// -------------------- Input Checker End --------------------

int sumN = 0;

void solve()
{
    int n = readIntSp(1, 2e5);
    int m = readIntLn(n, 1e9);
    sumN += n;
    int mx = -1;
    int ans_a = -1, ans_b = -1;
    for(int a = n; a <= min(2 * n - 1, m); a++)
    {
        int b = m / a * a;
        if(b - a > mx)
        {
            mx = b - a;
            ans_a = a, ans_b = b;
        }
    }
    cout << ans_a << " " << ans_b << endl;
}

int32_t main()
{
    ios::sync_with_stdio(0); 
    cin.tie(0);
    int T = readIntLn(1, 1000);
    for(int tc = 1; tc <= T; tc++)
    {
        // cout << "Case #" << tc << ": ";
        solve();
    }
    assert(sumN <= 2e5);
    readEOF();
    return 0;
}

Editorialist's Solution
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define pb push_back
#define all(_obj) _obj.begin(), _obj.end()
#define F first
#define S second
#define pll pair<ll, ll>
#define vll vector<ll>
ll INF = 1e18;
const int N = 1e5 + 11, mod = 1e9 + 7;
ll max(ll a, ll b) { return ((a > b) ? a : b); }
ll min(ll a, ll b) { return ((a > b) ? b : a); }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void sol(void)
{
    int n, m;
    cin >> n >> m;
    if (m < 2 * n)
    {
        cout << m << ' ' << m << '\n';
        return;
    }
    int mx = 0, a = m, b = m;
    for (int i = n; i < 2 * n; i++)
    {
        if (((m / i) * i) - i > mx)
            a = i, b = (m / i) * i, mx = ((m / i) * i) - i;
    }
    cout << a << ' ' << b << '\n';
    return;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    int test = 1;
    cin >> test;
    while (test--)
        sol();
}
1 Like

Hi all,
I have come up with an approach not sure its correct or not.

In this problem we know that m - m% n is for sure divisible by n , so we can limit our search to the range [m - m % n, m]. so by increasing n and checking for n ( [n, n + (m - m %n] ) we can check if any other pair other than (n, m - m % n) exists. which will be maximizing the difference also

is this correct or it could fail in any cases?

Unable to understand, why are you taking a=N to 2n ? you could have took it like a = n to 3n or 4n, But why 2n ?

1 Like

I think it will give TLE.

will it? because the loop will only run for m - m % n times :slightly_smiling_face:

I can’t get your idea. Can you write code for it?
And I think there is a mistake in your description: pair [n, n + (m - m %n)] is bad because n + (m - m % n) is always greater than m, so did you mean [n, m - m %n]?

sorry, there was mistake i meant to say [n , n + m % n]. thanks for pointing it out

for eg: consider 10 and 85 . we know that 80 is divisible by 10 so we can possibly choose 10 and 80 as and b. but if we want to check if there is any other pair that between 80 and 85 that can be divided by a number 10 between 15 (how i decided 15 is that ,10 + 85 %10 ) then we can choose that also i guess like in this case 12 and 84. this was what i was trying to do.

Max possible value of difference that can be obtained from 2N+1 to M is M-2N-1 (We cant take 2N since if 2N,M is a good pair then N,M also is one and has more diff). But even that max value can be obtained when we take a=N and b=M. So, M-M%N-N has the minimum value when M%n has max value which is N-1. So min(M-M%N-N)=M-2N-1. So, it is useless to go beyond 2N-1 to check for good pairs with max diff since we already have it in N to 2N-1

No, it’s not enough just to find another pair between n and n + (m % n). For example, n =179, m = 35084. 35084 is divisible by 179 so we can possibly choose 179 and 35084. But also we can choose 180 and 35100 (pair (180; 35100) is better than (179 and 35084) because difference is greater). There are some other better pairs. But answer in this case is (199, 35223).

So, as it is written in editorial, we should iterate a over [n; n + (m % n)] and for fixed a we can find b as m / a * a. Answer for the problem is such pair (a, b) that a - b is maximum. Implementation looks like this:

    int n, m;
    cin >> n >> m;

    int a_res = n, b_res = m / n * n;
    for (int a = n; a <= n + (m % n); a++) {
        int b = m / a * a;
        if (b - a > b_res - a_res) {
            a_res = a, b_res = b;
        }
    }

    cout << a_res << " " << b_res << "\n";