HDU 1576 (乘法逆元)

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

题目大意：求(A/B）mod 9973。但是给出的A是mod形式n，n=A%9973。

解题思路：

两种思路，一种从乘法逆元角度，另一种从扩展GCD推公式角度。

①乘法逆元：

先来看下逆元和乘法逆元的关系，对于A*X=B，有X=A^-1*B,A^-1就是普通的逆元了，在这里就是倒数。

如果A*X=B mod n，变成同余式了，那么A^-1依然是存在的，只不过不是倒数了，一般把同余之后的逆元称为乘法逆元。（ - -。好像这个定义是错的）。

题目如果是(A/B) mod 9973, 那就麻烦了，因为乘除法不支持mod同余运算，需要转化为逆元计算，乘法变除法，除法变乘法。且题目说gcd(B,9973)=1，所以取B的乘法逆元b=mod_reverse(B,9973)。

那么题目就转化成（A*b）mod 9973，再化简一下，（A%9973*b）%9973, 因为A%9973=n，

所以最后结果就是（n*b）mod 9973

 

#include "cstdio"
#define LL long long
LL ex_gcd(LL a,LL b,LL &x,LL &y)
{
    if(a==0&&b==0) return -1;
    if(b==0) {x=1;y=0;return a;}
    LL d=ex_gcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}
LL mod_reverse(LL a,LL n)
{
    LL x,y,d=ex_gcd(a,n,x,y);
    if(d==1) return (x%n+n)%n;
    else return -1;
}
int main()
{
    LL T,n,B;
    scanf("%I64d",&T);
    while(T--)
    {
        scanf("%I64d%I64d",&n,&B);
        LL x=mod_reverse(B,9973);
        printf("%I64d
",(n*x)%9973);
    }
}

②扩展GCD角度：

设A=9973*y+n，因为A%B=0，所以(9973*y+n)=B*x，其中x=A/B

移项，有B*x+9973*(-y)=n。

联想到扩展GCD的式子：B*X+9973*Y=1，两边都乘以n，B*(nX)+9973*(nY)=n。

这样x=nX，y=-nY，只要求出X和Y就行了，套扩展GCD模板即可。

注意这里扩展GCD求出的一组x和y可能都是负值，如果x%9973是错的，对负数取模的方法是(x%mod+mod)%mod.

 

#include "cstdio"
#define LL long long
LL ex_gcd(LL a,LL b,LL &x,LL &y)
{
    if(a==0&&b==0) return -1;
    if(b==0) {x=1;y=0;return a;}
    LL d=ex_gcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}
int main()
{
    LL T,n,B;
    scanf("%I64d",&T);
    while(T--)
    {
        scanf("%I64d%I64d",&n,&B);
        LL x,y;
        ex_gcd(B,9973,x,y);
        x*=n;
        printf("%I64d
",(x%9973+9973)%9973);
    }
}

12168956

2014-11-13 00:56:37

Accepted

1576

0MS

228K

519B

C++

Physcal