HDU 1576 A/B

题意： 略

根据题意 gcd(B,9973) == 1, 那么我们可以根据这个式子大致知道我们要构造的式子一定是  x*B + y*9973 == gcd(B,9973) == 1, 大致是这个类型，然后朝着这个目标构造就行了。

 

推导过程：

设：（A/B）%9973 = k

则： A/B = k * 9973*x   (x属于未知的系数)

       A = k*b + 9973*x*B

因为： A%9973 == n 故：k*B%9973 == n

则： k*b = n + 9973*y (这个时候这个式子已经非常满足我们刚才所说的式子了)

再进行一步转换： (k/n)*B + (-y/n)*9973 = 1 = gcd(B, 9973)

=======================================================================================================

 

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<map>
using namespace std;
typedef long long LL;
const int INF = 1e9+7;
const int maxn = 115;
const int MOD = 9973;

void ExGcd(LL a,LL b,LL& x,LL& y)
{
    if(b == 0)
    {
        x = 1, y = 0;
        return ;
    }

    ExGcd(b, a%b, x, y);
    LL t = x;
    x = y;
    y = t - (a/b)*y;
}

int main()
{
    LL n, B;
    int T;
    scanf("%d", &T);
    while( T-- )
    {
        scanf("%I64d%I64d",&n, &B);
        LL x, y, ans;
        ExGcd(B, 9973, x, y);
        ans = (x%MOD + MOD)%MOD;
        ans =  (ans*n)%MOD;
        printf("%I64d
", ans) ;
    }
    return 0;
}