nyoj 小珂的苦惱 144 （簡單拓展歐幾裡得）

小珂的苦惱

時間限制： 1000 ms  |           記憶體限制： 1000 KB 難度：2

描述

    小珂是一名國中生，她現在很苦惱，因為老師布置了一個讓她苦惱的作業，你能不能幫助她呢？題目資訊如下。

        已知二進制一次方程 a*x+b*y=n， 判斷這個二進制一次方程有沒有整數解，x,y為未知數，其中a，b，n都為整數且不等于零，同時滿足0<a,b,n<2^16-1。

輸入

第一行有一個整數0<n<=1000000表示有 n組測試資料,接下來的每一行有三個整數分别是a,b,n

輸出

存在整數x和y使得方程有解，輸出“Yes”，否則輸出“No”

樣例輸入

2      

2 4 2      

3 9 7      

樣例輸出

Yes      

No      

#include<stdio.h>
#include<string.h>
#define ll long long
/*int gcd(int a,int b,int &x,int &y)
{
	if(!b)
	{
		x=1;
		y=0;
		return a;
	}
	int ans=gcd(b,a%b,x,y);
	int tmp=x;
	x=y;
	y=tmp-a/b;
	return ans;
}*/
int gcd(int a,int b)//因為題意隻讓判斷是否有解，所上面的就逾時了。 
{
	return b==0?a:gcd(b,a%b);
}
int main()
{
	int t;
	int a,b,n,x,y;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d%d",&a,&b,&n);
		int d=gcd(a,b);
		if(n%d!=0)
			printf("No\n");
		else
			printf("Yes\n");
	}
	return 0;
}