HDU 1576 A/B 数论水题

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

写了个ex_gcd的模板...太蠢导致推了很久的公式

这里推导一下: 

因为　　1 = BX + 9973Y       　　　　　 ----------------①

且　　　n = Bk - floor(A/9973) * 9973      ----------------②

①*n即    n = BnX + nY * 9973

那么 k = nX 

k = A/B ...而k%9973为所求

(n*X)%9973 = (n%9973 * X%9973)%9973 = (n%9973 * (X%9973+9973)) % 9973

那么EX_GCD求逆元得到X,因为X%9973可能为负数,所以转换成正数取模

pair<LL,LL> ex_gcd(LL a,LL b){
  if(b == 0) return make_pair(1,0);
  pair<LL,LL> t = ex_gcd(b,a%b);
  return make_pair(t.second , t.first - (a / b) * t.second);
}
int main()
{
    int T,n,k;
    cin>>T;
    while(T--){
        cin>>n>>k;
        pair<LL,LL> p = ex_gcd(k,9973);
        LL  q = p.first % 9973 + 9973;
        LL ans = (q * n) % 9973;
        cout<<ans<<endl;
    }
    return 0;
}