HDU-1576: A/B（乘法逆元+拓展欧几里得 | 费马小定理）

数论

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

分析：要求解A/B%9973，已知A%9973，那么我们就需要求出$B^{-1}$%9973的值。可以使用拓展欧几里得定理或者费马小定理求得B的逆元。

拓展欧几里得

ax+by=gcd(a,b)，因此Bx+9973y=GCD（B，9973）=1，求得的x就是B对9973的逆元$B^{-1}$。再进行计算。

• 完整代码：

#include<stdio.h>
#define LL long long
#define mod 9973
LL x,y;
void ex_gcd(LL a,LL b)
{
    if(b==0)
    {
        x=1;
        y=0;
        return;
    }
    ex_gcd(b,a%b);
    int t=x;
    x=y;
    y=t-a/b*y;
}
int main()
{
    int t,n,b;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&b);
        ex_gcd(b,mod);
        if(x<0)
            x+=mod;
        printf("%lld\n",(n*(x%mod))%mod);
    }
    return 0;
}

费马小定理

由费马小定理可以推得：
B对mod的逆元（$B^{-1}$）等于$B^{mod-2}$%mod，这个可以用快速幂取模来求得。

• 完整代码：

#include<stdio.h>
#define LL long long
#define mod 9973
LL quick(LL x,LL m,LL n)//x^m%n
{
    LL ans=1;
    while(m>0)
    {
        if(m%2==1)
            ans=ans*x%n;
        x=x*x%n;
        m=m/2;
    }
    return ans;
}
int main()
{
    LL t,n,b,ans;
    scanf("%lld",&t);
    while(t--)
    {
        scanf("%lld%lld",&n,&b);
        ans=quick(b,mod-2,mod);
        printf("%lld\n",(n*ans)%mod);
    }
    return 0;
}