My issue
lets take two number with gcd as G, then we can represent two number as Ga, Gb (a<b)
In First Iteration : Alice will choose the bigger number (Gb) and replace it with G
In Second Iteration : LCM OF (Ga, G) will be Ga so he will replace the same number , so no difference
In Third Iteration : GCD will be G and Ga will replace by G
and both number will become same hence we should return 2G as sum
Can anyone tell me why this logic doesnt work
int a,b,k; cin>>a>>b>>k;
int gcd_ab= gcd(a,b);
// cout<<gcd_ab<<endl;
int ans= min(a,b)+gcd_ab;
if(k>2) ans=2gcd_ab;
cout<<ans<<endl;
My code
#include<bits/stdc++.h>
//INT_MIN
//INT_MAX
using namespace std;
#define int long long
void pre_io(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
}
int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
void solve(){
int a,b,k; cin>>a>>b>>k;
int gcd_ab= gcd(a,b);
// cout<<gcd_ab<<endl;
int ans= min(a,b)+gcd_ab;
if(k>2) ans=2*gcd_ab;
cout<<ans<<endl;
}
int32_t main(){
pre_io();
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
int t; cin>>t;
while(t--)
solve();
return 0;
}
Problem Link: GCDLM Problem - CodeChef