一些基本概念： 乘法逆元，是指数学领域群G中任意一个元素a，都在G中有唯一的逆元a‘,具有性质a×a'=a'×a=e，其中e为该群的单位元。   用[a]n代表x%n=a.的所有满足条件的x所组成的集合，其中a为集合中最小非负整数，用最小的非负整数来代表整个集合，即[a]n={a+k*n,k∈Z) Zn={ [0]n, [1]n ,[2]n ,[3]n ,…, [n-1]n } 在模n乘法群(Zn*,  *)中，Zn*={[a]n∈Zn,且gcd(a,n)=1}，单位元为[1]n,不在群里的元素没有关于模n的逆元，若某个[a]n有逆元x，那么[a]n *  [ x ]n===1(mod n)（一个元素与其对应的逆元进行运算结果为单位元），转换为ax+ny=1,a和n关于整数x，y线性组合，故gcd(a,n)=ax+ny=1. 所以某个元素在模n乘法运算下存在逆元，必须gcd(a,n)=1. 由存在逆元的条件gcd(a,n)=ax+ny=1.可以用exgcd求出x，这里求出的x可能不是最小非负，要将其转化为最小非负（代表元素)。另,x有无穷多个解X0=x+k*n,k∈Z,将解得的x化为代表元素，也即a的逆元。
题目思路：B是可以整除A的，且B与9973互质，说明B的模9973乘法运算存在逆元，用X表示B的逆元，那么(A/B)%9973可以转化为(n*X)%9973.所以题目要求求出X即可 B*x=1(mod)9973(x为B关于9973的逆元)   => B*x + 9973*y = 1.用扩展欧几里得算出x就是B关于模9973的逆元 (A/B)%9973 = (A*x)%9973 #include using namespace std; //求 （A/B)%9973 且gcd(B,9973)=1,B能整除A void exgcd(int a,int b,int d,int &x,int &y) { if(!b) { x=1;y=0; d=a; } else { exgcd(b,a%b,d,y,x); y-=x*(a/b); } } int main() { int n,b; int t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&b); int d,x,y; exgcd(b,9973,d,x,y); x=(x%9973+9973)%9973;//解得B的逆元 int ans=(n*x)%9973; printf("%d ",ans); } }
费马小定理求逆元： a^(p-1) ≡1 (mod p)  p是质数，a与p互质 两边同除以a a^(p-2) ≡1/a (mod p) 1/a就是a关于模p的逆元。 逆元x=a^(p-2) (mod p)快速幂解出来就行了 #include #define ll long long using namespace std; int pow(int a,int n,int p) { int ret=1; while(n) { if(n&1) ret=((ll)ret*a)%p; a=((ll)a*a)%p; n>>=1; } return ret; } int main() { int n,b; int t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&b); b=pow(b,9973-2,9973); b=((b%9973)+9973)%9973; printf("%d ",(n*b)%9973); } }