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:
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();
}
