PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Lavish Gupta
Tester: Harris Leung
Editorialist: Trung Dang
DIFFICULTY:
1546
PREREQUISITES:
GCD, LCM
PROBLEM:
Given two positive integers a and b, we define f(a,b)=lcm(a,b)−gcd(a,b), where lcm denotes the lowest common multiple and gcd denotes the greatest common divisor.
Chef has a positive integer N. He wonders, what is the maximum value of f(a,b) over all pairs (a,b) such that a and b are positive integers, and a+b=N?
EXPLANATION:
Quick explanation: We find the pair a < b such that gcd(a, b) = 1 and b - a is as small as possible. In details:
- If N is odd, a = \lfloor N / 2 \rfloor and b = \lceil N / 2 \rceil.
- If N is divisible by 4, a = N / 2 - 1 and b = N / 2 + 1.
- If N \equiv 2 \pmod{4}, a = N / 2 - 2 and b = N / 2 + 2.
There is one small edge case to this: when N = 2, a = b = 1.
To see how this works, note that since lcm(a,b) \cdot gcd(a,b) = ab, or lcm(a,b) = \frac{ab}{gcd(a,b)}, intuitively, we have two goals simultaneously when trying to maximize f(a, b):
- Minimizing gcd(a, b). This can be done by making gcd(a, b) = 1.
- Maximize ab. This can be done by making a and b as close to each other as possible.
Hence we have the aforementioned algorithm, where we can easily prove that in every case, a and b are the closest pair of numbers such that gcd(a, b) = 1. Proving that this strategy indeed maximizes f(a, b) follows naturally from that: we can prove that any pair of (a, b) closer than the proposed pair gives a smaller f(a, b), and any pair (a, b) further than the proposed pair has product ab less than the proposed f(a, b), and hence its f(a, b) must be less than the proposed f(a, b).
TIME COMPLEXITY:
Time complexity is O(1) for each test case.
SOLUTION:
Setter's Solution
//Utkarsh.25dec
#include <bits/stdc++.h>
#define ll long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define vl vector <ll>
#define all(c) (c).begin(),(c).end()
using namespace std;
ll power(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll modInverse(ll a){return power(a,mod-2);}
const int N=500023;
bool vis[N];
vector <int> adj[N];
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int 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(1 == 0);
}
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 solve()
{
int n=readInt(2,1000000000,'\n');
if(n==2)
{
cout<<0<<'\n';
return;
}
if(n%2==1)
{
long long x=n/2,y=x+1;
cout<<(x*y-1)<<'\n';
}
else
{
long long x=n/2,y=n/2;
x--,y++;
if(x%2==0)
x--,y++;
cout<<(x*y-1)<<'\n';
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL),cout.tie(NULL);
int T=readInt(1,100000,'\n');
while(T--)
solve();
assert(getchar()==-1);
cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
const ll mod=998244353;
const int N=2e6+1;
ll a[N];
int main(){
ios::sync_with_stdio(false);
int t;cin >> t;
while(t--){
ll n;cin >> n;
if(n==2) cout << "0\n";
else if(n%2==1) cout << (n-1)/2*(n+1)/2-1 << '\n';
else if(n%4==0) cout << (n/2-1)*(n/2+1)-1 << '\n';
else cout << (n/2-2)*(n/2+2)-1 << '\n';
}
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t; cin >> t;
while (t--) {
int n; cin >> n;
if (n == 2) {
cout << "0\n";
} else if (n % 2 == 1) {
cout << 1LL * (n / 2) * (n / 2 + 1) - 1 << '\n';
} else if (n % 4 == 0) {
cout << 1LL * (n / 2 - 1) * (n / 2 + 1) - 1 << '\n';
} else {
cout << 1LL * (n / 2 - 2) * (n / 2 + 2) - 1 << '\n';
}
}
}
