NITGOC - Editorial

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;
}
6 Likes

Thank you for editorial. Actually in my submission I was implicitly writing euclids algorithm for getting 1, 1 and later realised its same as gcd(A,B) = 1

2 Likes

Well i filled my whole page using tree adding either a or b and checking all possible combinations i can get.
I just made conclusion after seeing them that gcd = 1 should hold, but didn’t knew why it was like that. Now i get to know that it was just based on properties of gcd. Wow!

Thank you :slight_smile:

How to approach such problems since i had tried it but i didn’t thought of that i have to find gcd here?