hdu 1576 A/B

http://acm.hdu.edu.cn/showproblem.php?pid=1576

这是一道扩展GCD题，只要找出方程就可以用模板了，n=A%9973可以得到A=9973*y+n，设A/B=x,所以A=B*x;可以得到方程B*x-9973*y=n，解方程就可以了，若有不明白的地方请看

http://www.cnblogs.com/yuelingzhi/archive/2011/08/13/2137582.html

代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
int exgcd(int a,int b,int &x,int &y)
{
    if(b)
    {
        int d=exgcd(b,a%b,x,y);
        int t=x;
        x=y;
        y=t-a/b*y;
        return d;
    }
    else
    {x=1;y=0;return a;}
}
int main()
{
    int t,n,b,x,y,d,k;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&b);
        d=exgcd(b,9973,x,y);
        k=9973/d;
        x*=(n/d);
        x=(x%k+k)%k;
        printf("%d\n",x%9973);
    }
    return 0;
}