Problem link : CodeChef: Practical coding for everyone
Initially , we have 1 red ball and 1 black ball. He have to get rest of the X-1 Red balls and Y-1 Black balls.
Initial State : 1 red ball and 1 black ball
Final State : X red balls and Y balck balls
Let look out this,
gcd(a, b ) = gcd(a + b, b) = gcd( a, a + b)
From this it is found that , if the numbers have the same gcd then it is always possible to get to the final state
Since initial state has GCD = 1
So if gcd(X, Y) ==1 , then it is possible to buy rest of the balls from the market. Otherwise NOT POSSIBLE.
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD 1000000007
ll gcd(ll a, ll b){
if(b == 0){
return a;
}
return gcd(b, a%b);
}
int main(){
ll test;
cin >> test;
while(test--){
ll x, y;
cin >> x >> y;
if(gcd(x,y) == 1){
cout << "YES" << endl;
}else{
cout << "NO" << endl;
}
}
return 0;
}