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; } 
    
   
  

?