NYOJ144 小珂的苦惱 (擴展gcd)

題目描述：

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

已知二元一次方程 a*x+b*y=n， 判斷這個二元一次方程有沒有整數解，x,y為未知數，其中a，b，n都為整數且不等於零，同時滿足0 輸入第一行有一個整數0
輸出存在整數x和y使得方程有解，輸出“Yes”，否則輸出“No”

樣例輸入

2

2 4 2

3 9 7

Yes

No

題目分析：

對於gcd(a,b)=ax+by,一定存在唯一的x和y使等式成立

AC代碼：

/**
 *對於gcd(a,b)=ax+by,存在唯一的x和y使等式成立
 */
#include
#include
#include
using namespace std;
int gcd(int a,int b)
{
    while(b){
        int r=a%b;
        a=b;
        b=r;
    }
    return a;
}
int main()
{
    int a,b,c,p,t;
    scanf(%d,&t);
    while(t--){
        scanf(%d%d%d,&a,&b,&c);
        p=gcd(a,b);
        if(c%p==0){//c是p的倍數即可
            printf(Yes
);
        }
        else printf(No
);
    }
    return 0;
}