A Diophantine equation is a polynomial equation, usually in two or more unknowns, such that only the integral solutions are required. An Integral solution is a solution such that all the unknown variables take only integer values.
Given three integers A, B, C representing a linear equation of the form: Ax + By = C. Determine if the equation has a solution such that x and y are both integral values.
 
Example 1:
Input: 
A = 3
B = 6
C = 9 
Output: 
1 
Explanation:
It is possible to
write A, B, C in the
for 3 + 6 = 9
Example 2:
Input: 
A = 4
B = 2
C = 3
Output: 
0 
Explanation:
It is not possible to
represent A, B, C in 
Diophantine equation form.
Your Task:
You don't need to read input or print anything. Your task is to complete the function isPossible() which takes three integer values A, B, C as input parameters and returns 1 if the solution for x and y exist otherwise return 0.
 
Expected Time Complexity: O(log N)
Expected Space Complexity: O(1)
 
Constraints:
1 <= A,B,C <= 10^{5}

Difficulty: EASY
Tags: Mathematics
Expected Time Complexity: O(log N)
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3

class Solution:
    def isPossible(self,A,B,C): 
        # code here

Solutions:
import math

class Solution:

	def isPossible(self, A, B, C):
		k = math.gcd(A, B)
		if C % k == 0:
			return 1
		else:
			return 0


class Solution:

	def gcd(self, a, b):
		min_num = min(a, b)
		while min_num:
			if a % min_num == 0 and b % min_num == 0:
				break
			min_num -= 1
		return min_num

	def isPossible(self, A, B, C):
		return 1 if C % self.gcd(A, B) == 0 else 0


class Solution:

	def gcd(self, a, b):
		if b == 0:
			return a
		return self.gcd(b, a % b)

	def isPossible(self, A, B, C):
		return 1 if C % self.gcd(A, B) == 0 else 0


class Solution:

	def isPossible(self, A, B, C):
		divisor = B
		dividend = A
		while divisor != 0:
			temp = divisor
			divisor = dividend % divisor
			dividend = temp
		if C % dividend == 0:
			return 1
		else:
			return 0


class Solution:

	def calc_gcd(self, a, b):
		if b == 0:
			return a
		return self.calc_gcd(b, a % b)

	def isPossible(self, a, b, c):
		gcd = self.calc_gcd(a, b)
		if c % gcd == 0:
			return 1
		else:
			return 0


class Solution:

	def isPossible(self, A, B, C):
		if N % B == 0 or N % A == 0:
			return 1
		import math
		if A < B:
			(A, B) = (B, A)
		for i in range(1, N + 100000):
			m = C - A * i
			if m % B == 0:
				return 1
		return 0


class Solution:

	def isPossible(self, A, B, C):

		def gcd(x, y):
			if x == 0:
				return y
			return gcd(y % x, x)
		return 1 if C % gcd(A, B) == 0 else 0
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(A, B, N) = input().split()
		A = int(A)
		B = int(B)
		N = int(N)
		ob = Solution()
		print(ob.isPossible(A, B, N))


class Solution:

	def isPossible(self, A, B, c):

		def euclid(a, b):
			if b == 0:
				return (a, 1, 0)
			(g, x1, y1) = euclid(b, a % b)
			x = y1
			y = x1 - a // b * y1
			return (g, x, y)
		(g, x, y) = euclid(A, B)
		if c % g == 0:
			return 1
		else:
			return 0


from math import gcd

class Solution:

	def isPossible(self, A, B, C):
		if C % gcd(A, B) == 0:
			return 1
		return 0


import numpy
import math

class Solution:

	def isPossible(self, A, B, C):
		bigger = min(A, B)
		true = [True] * (bigger + 1)
		for i in range(2, int(math.sqrt(bigger)) + 1):
			if true[i]:
				for x in range(i * 2, bigger, i):
					true[x] = False
		FA = []
		curr = A
		for i in range(len(true)):
			if i == 0 or i == 1:
				continue
			else:
				while curr % i == 0 and true[i]:
					curr = curr // i
					FA.append(i)
			if i > curr:
				break
		FB = []
		curr = B
		for i in range(len(true)):
			if i == 0 or i == 1:
				continue
			else:
				while curr % i == 0 and true[i]:
					curr = curr // i
					FB.append(i)
			if i > curr:
				break
		common = []
		for i in FA:
			if i in FB:
				FB.remove(i)
				common.append(i)
		HCF = numpy.prod(common)
		if C % HCF == 0:
			return 1
		else:
			return 0