首页 > ACM题库 > HDU-杭电 > HDU 1576 A/B-数论应用-[解题报告] Pascal
2013
12-12

HDU 1576 A/B-数论应用-[解题报告] Pascal

A/B

问题描述 :

要求(A/B)%9973,但由于A很大,我们只给出n(n=A%9973)(我们给定的A必能被B整除,且gcd(B,9973) = 1)。

输入:

数据的第一行是一个T,表示有T组数据。
每组数据有两个数n(0 <= n < 9973)和B(1 <= B <= 10^9)。

输出:

对应每组数据输出(A/B)%9973。

样例输入:

2
1000 53
87 123456789

样例输出:

7922
6060

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;
}

 

解题报告转自:http://www.cnblogs.com/Felix-F/p/3264841.html