在做题之前希望大家先学习欧几里德及其扩展，以下是大牛的解析
欧几里德及其扩展解析
小珂的苦恼
时间限制： 1000 ms | 内存限制： 10000 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 来源 [iphxer]原创 上传者 iphxer
代码：
#include<stdio.h>
int gcd(int a,int b){
return b ? gcd(b,a%b) : a;
}
bool linear_equation(int a,int b,int c){
int d = gcd(a,b);
if(c % d ) return false;
else return true;
}
int main(){
int kcase,a,b,n;
scanf("%d",&kcase);
while(kcase--){
scanf("%d%d%d",&a,&b,&n);
if(linear_equation(a,b,n)) printf("Yesn");
else printf("Non");
}
return 0;
}
整数性质
时间限制： 500 ms | 内存限制： 65535 KB
难度：1
描述我们知道，在数学中，对于任意两个正整数a和b，必定存在一对整数s、t使得sa+tb=gcd(a,b)。
输入 多组测试数据。每组数据输入两个非负整数a和b且a+b>0且a不等于b。
其中0<=a,b<100000。 输出 输出满足条件的 s 和 t 。 样例输入
2 43 8737 635 样例输出
1 03 -1193 -224 提示 运用欧几里得定理求得的才是正确答案。 来源 原创 上传者 TC_李远航
代码：
#include<stdio.h>
int exgcd(int a,int b,int& x,int& y){
if(!b){
x=1;
y=0;
return a;
}
int r = exgcd(b,a%b,y,x);
y -= a/b*x;
return r;
}
int main(){
int a,b,x,y;
while(~scanf("%d%d",&a,&b)){
exgcd(a,b,x,y);
printf("%d %dn",x,y);
}
return 0;
}
