SPOJ MAY99_3 - Easy Jug

Problem link

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 wiki page. :D

reference

A solution in c++

	#pragma GCC optimize("Ofast,no-stack-protector")
	#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native"
	#include<bits/stdc++.h>

	using namespace std;

	/// Typedef
	typedef long long ll;

	#define sc1(a) scanf("%lld",&a)
	#define sc2(a,b) scanf("%lld %lld",&a,&b)

	#define pf1(a) printf("%lld\n", a)
	#define pf2(a,b) printf("%lld %lld\n",a,b)

	#define size1 300005


	int main() {

	//seive();
	//preCal();

	ll tc, num, t = 1, choose;

	//freopen("/opt/Coding/clion code/input.txt", "r", stdin);
	//freopen("/opt/Coding/clion code/output.txt", "w", stdout);

	ll a, b, c;

	sc1(tc);

	while (tc--){

	sc2(a, b);
	sc1(c);

	ll mx = max(a, b);

	if(mx < c){
	cout << "NO" << endl;
	}
	else{
	ll common = __gcd(a, b);
	if(c % common == 0) cout << "YES" << endl;
	else cout << "NO" << endl;
	}
	}

	return 0;
	}