题目大意：
已知线性方程ax+by=1; 输入a, b的值, 要求输出整数解x, y的值(输出x, y的最小整数解), 若没有解, 输出"sorry".
分析：
求线性方程的解用扩展欧几里得算法，令gcd(a,b)=d, 如果1是d的倍数表示方程有解, 否则无解.
代码如下:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <fstream>
#include <ctime>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <set>
#include <map>
#include <list>
#include <stack>
#include <queue>
#include <iterator>
#include <vector> using namespace std; #define LL long long
#define INF 0x3f3f3f3f
#define MOD 1000000007
#define MAXN 10000010
#define MAXM 1000010 LL extend_gcd(LL a, LL b, LL &x, LL &y)
{
if(b == )
{
x = ;
y = ;
return a;
}
else
{
LL r = extend_gcd(b, a%b, y, x);
y -= x*(a/b);
return r;
}
} int main()
{
int a, b;
while(scanf("%d%d", &a, &b)==)
{
LL t, p;
LL ans = extend_gcd(a, b, t, p);
if(%ans)
printf("sorry\n");
else
{
LL x = *t/ans; //特解
x = (x%(b/ans)+(b/ans))%(b/ans); //最小整数解
LL y = (-a*x)/b;
printf("%lld %lld\n", x, y);
}
} return ;
}