Spoj MAY99_3

Logic:

So when we start to solve a problem first approach should always be brute force solution if we have no idea about problem's optimized solution, so for this problem brute force solution will be a recursion function where we try all possible cases and if we get our expected solution then return YES otherwise go on.
Now here question is when we will stop or what will be our termination condition well in this problem if we reach again same condition then we stop.

pseudocode of recursive function:-

Function(Water_in_JugA, Water_in_JugB) {
              //We can fill any jug completely 
              Answer = Function(Fill_Full_JugA, Water_in_JugB)
              Answer = Answer or Function(Water_in_JugA, Fill_Full_JugB)
             
              //We can empty any jug entirely 
             Answer = Answer or Function(0, Water_in_JugB)
             Answer = Answer or Function(Water_in_JugA, 0)

            //Transfer as much water from Jug A to Jug B, till Jug A gets empty or Jug B is completely filled or vice versa
            
            Answer = Answer or Function(Fill_JugA_until_JugA_Full_or_JugB_empty, Water_in_JugB - how much water we use to fill JugA)
            Answer = Answer or Function(Water_in_JugA - how much water we use to fill JugB, Fill_JugB_until_JugB_Full_or_JugA_empty) 
  
}

Now someone will say hey it will take O(Limit_of_JugA * Limit_of_JugB)
and that mean it will be O(10^16) because at most Limit_of_JugA can be 10^8
and yes he is right.
Now again question arise that then how we can solve it well our solution is in brute force solution
try some cases using above function and analyze it.

................ (analyzing :P)

 so when we analyze our brute force solution most critical point here is third one transfer water from A/B to B/A which can be write down as F(A, B) -> F(min(A + B, A), B - min(A, A + B)) and using other two points we can always fill one of our jug so now if we can find domain of elements we can get in our brute force solution then we can insure that we can get solution or not.
look this sequence if you find any relation

try some examples for F(A, B) -> F(min(A + B, A), B - min(A, A + B))

F(2, 5) -> F(2, 3) -> F(2, 1)

F(5, 2) -> not a valid state

F(3, 9) -> F(3, 6) -> F(3, 3) -> F(3, 0)

so if you see sequence closely you get it solution right.
someone will say no its okay for more we will try to examine our equation

F(A, B) -> F(min(A + B, A), B - min(A, A + B))
as we know if A > B then there will be no more steps but we can swap B, A right
now again why? (read problem again and convenience yourself that we can :D )

so we can right that A < B
F(A, B) -> F(min(A + B, A), B - min(A, A + B))
and if A > B then
F(B, A) -> F(min(A + B, B), A - min(B, A + B))

now again try examples
F(2, 5) -> F(2, 3) -> F(2, 1) -> F(1, 2) -> F(1, 1) -> F(1, 0) -> F(0, 1)

F(5 , 2) -> F(2, 5) same sequence

F(3, 9) -> F(3, 6) -> F(3, 3) -> F(3, 0) -> F(0, 3)

now again we analyze this sequence we can say that F(A, B) -> F(A , KA - B) or vice versa
that mean we can get expected water in any jug if it is equal to any factor of their Limit's gcd
for more details on GCD  read  wikipage. :D

Below you can see code also

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cctype>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <functional>
using namespace std; 
#define DEBUG(x) cout << '>' << #x << ':' << x << endl;
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define FORD(i,a,b) for(int i=(a);i>=(b);i--)
inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }
const int INF = 1<<29;
typedef long long ll;
inline int two(int n) { return 1 << n; }
inline int test(int n, int b) { return (n>>b)&1; }
inline void set_bit(int & n, int b) { n |= two(b); }
inline void unset_bit(int & n, int b) { n &= ~two(b); }
inline int last_bit(int n) { return n & (-n); }
inline int ones(int n) { int res = 0; while(n && ++res) n-=n&(-n); return res; }
template<class T> void chmax(T & a, const T & b) { a = max(a, b); }
template<class T> void chmin(T & a, const T & b) { a = min(a, b); }
/////////////////////////////////////////////////////////////////////


int main()
{
int T;
scanf("%d", &T);

while(T--) {
int x;
int y;
int z;
scanf("%d%d%d", &x, &y, &z);
if(max(x, y) < z) {
puts("NO");
} else if (z % __gcd(x, y) == 0){
puts("YES");
} else {
puts("NO");
}
}
    return 0;
}


Happy Coding :)