HDU 1576 A/B（扩展欧几里德变形）

程序员润华技术 2022年11月14日

0 收藏 757 点赞 2,917 浏览 970 个字

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1576

Problem Description要求(A/B)%9973，但因为A非常大，我们仅仅给出n(n=A%9973)(我们给定的A必能被B整除。且gcd(B,9973) = 1)。 Input数据的第一行是一个T，表示有T组数据。

每组数据有两个数n(0 <= n < 9973)和B(1 <= B <= 10^9)。Output相应每组数据输出(A/B)%9973。

Sample Input

2
1000 53
87 123456789

Sample Output

7922
6060

AuthorxhdSource

field=problem&key=HDU+2007-1+Programming+Contest&source=1&searchmode=source” style=”color:rgb(26,92,200); text-decoration:none”>HDU 2007-1 Programming Contest

PS:

n = A%9973, 设A / 9973 = y;

A / B = x —>>>> A = B * x;

那么就有： B*x – 9973 * y = n;

代码例如以下：

#include <cstdio>
#include <cstring>
#include <cmath>
typedef __int64 LL;LL exgcd(LL a,LL b,LL &x,LL &y)
{
    if(b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    LL r = exgcd(b,a%b,x,y);
    LL t = x;
    x = y;
    y = t-a/b*y;
    return r;
}LL cal(LL a, LL b, LL c)
{
    LL x, y;
    LL tt = exgcd(a, b, x, y);
    if(c%tt)
        return -1;
    x *= c/tt;
    b/=tt;
    if(b < 0)
        b = -b;
    LL ans = x%b;
    if(ans < 0)
        ans += b;
    return ans;
}
int main()
{
    LL n, b;
    LL t;
    scanf("%I64d",&t);
    while(t--)
    {
        scanf("%I64d%I64d",&n,&b);
        LL ans = cal(b,9973,n);
        if(ans == -1)
            printf("Impossible\n");
        else
            printf("%I64d\n",ans);
    }
    return 0;
}