HDU1576 A/B（乘法逆元）

题目的代数系统可以看作整数模9973乘法群？然后存在乘法逆元。

于是题目要求$A div B pmod {9973} $其实就相当于求$A imes B^{-1}pmod {9973} $。

只要求出B的逆元就OK了。

计算模n下的乘法逆元可以用用扩展欧几里得算法求解，即解下面的线性同余方程：

$$ Ax equiv 1 pmod {n} $$

#include<cstdio>
#include<cstring>
using namespace std;
#define mod(x,y) (((x)%(y)+(y))%(y))
#define lld long long
lld exgcd(lld a,lld b,lld &x,lld &y){
    if(b==0){
        x=1; y=0;
        return a;
    }
    lld d=exgcd(b,a%b,x,y);
    lld t=y;
    y=x-a/b*y;
    x=t;
    return d;
}
lld ine(lld a,lld n){
    lld x,y;
    exgcd(a,n,x,y);
    return mod(x,n);
}
int main(){
    lld a,b;
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%lld%lld",&a,&b);
        printf("%lld
",a*ine(b,9973)%9973);
    }
    return 0;
}