class="markdown_views prism-dracula"> http://acm.hdu.edu.cn/showproblem.php?pid=1576
先简介下扩展欧几里得算法：
据说可以证明方程ax+by=gcd(a，b)必然有解，而且不止一组解（gcd指最大公约数）
朴素的欧几里得算法就是辗转相除法，用来求gcd的
因为gcd(a，b)=gcd(b，a mod b)=gcd(a mod b，b mod (a mod b))=…
最后会有一方等于0，就能求出gcd(a，b)，这就是辗转相除法 扩展欧几里得算法可以解出方程ax+by=gcd(a，b)的一组解，假设a>b>=0
以下是一段简单的推导：
ax1+by1=bx2+(a%b)y2
             =bx2+(a-[a/b]*b)y2
             =ay2+bx2-[a/b]*by2
             =ay2+b(x2-[a/b]*y2)
至此可知x1=y2，y1=x2-[a/b]*y2
（注：%表示mod，a-[a/b]*b等同于a mod b，[]表示向下取整） 因此，只要知道x2，y2就能知道x1，y1，而x2，y2也能通过x3，y3得知，这样往下递推到b=0为止 回到题目中，设X=A/B，
则
n=A%9973
  =A+[A/9973]*9973
  =XB+[A/9973]*9973 设x*B+9973*y=gcd(B，9973)=1，用扩展欧几里得算法可以算出这个方程的一组解，即x和y可知
方程两边乘以n得x*n*B+y*n*9973 = n = XB+A/9973*9973
对比式子两边可知x*n=X
那么知道了x就知道X了，X就是A/B
X%9973（即x*n%9973）就是题目要的答案 但问题又来了，扩展欧几里得算法算出的x是负数怎么办？
负数取模再加一份模得到正数，然后输出即可，即x*n%9973+9973
（由于本人暂时也不太明白为何负数取模要想得到正数结果在这题当中可以这样转化，加上时间紧迫，只能回头再做补充了，至少代码能A）
#include using namespace std; int exGcd(int a, int b, long long &x, long long &y) { if (b == 0) { x = 1; y = 0; return a; } int r = exGcd(b, a%b, x, y); int t = x; x = y; y = t - a / b * y; return r; } int main() { int T; cin >> T; long long n, B; long long x, y; for (T; T > 0; T--) { cin >> n >> B; exGcd(B, 9973, x, y); cout << x*n % 9973 + 9973 << endl; } return 0; }