[HDU1576] A/B（扩展欧几里得）

传送门

n = A % 9973 -> n = A - A / 9973 * 9973

设 x = A / B（题目所述，B|A） -> A = B * x

所以 B * x - A / 9973 * 9973 = n

设 y = A / 9973

则 B * x - 9973 * y = n

B 和 n 已知， gcd(B, 9973) == 1

所以可以求出 B * ｘ + 9973 *(- y) == 1 时的 x 的解

然后 x 再 * n，最后求 (x % 9973 + 9973) % 9973 即为答案

——代码

 #include <cstdio>

 inline void exgcd(int a, int b, int &x, int &y)

 {

     if(!b){x = , y = ; return;}

     exgcd(b, a % b, y, x);

     y -= a / b * x;

 }

 int main()

 {

     int n, b, x, y, T;

     scanf("%d", &T);

     while(T--)

     {

         scanf("%d %d", &n, &b);

         exgcd(b, , x, y);

         x *= n;

         printf("%d\n", (x %  + ) % );

     }

     return ;

 }

巴特西

[HDU1576] A/B（扩展欧几里得）

最新文章

热门文章