#16_CEQU.txt

Linear Diophantine Equations

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.

For linear Diophantine equation equations, integral solutions exist if and only if, the GCD of coefficients of the two variables divides the constant term perfectly.
In other words the integral solution exists if, GCD(a ,b) divides c.

#include<stdio.h>
gcd(int m,int n){
   if(n==0)

  return m;

 else 

  return gcd(n,m%n);

}

int main(){

 int a,b,c,t,g,e=1;

 scanf("%d",&t);

 while(t--){

  scanf("%d %d %d",&a,&b,&c);

  g=gcd(abs(a),abs(b));

  if(c%g==0)

   printf("Case %d: Yes\n",e);

  else 

   printf("Case %d: No\n",e);

   e++;

 }

 return 0;

}