[数据结构与算法]特殊的同余方程——逆元

同余方程 ax ≡ 1（mod n），gcd（a，n）=1时有解。

这时称求出的x为a的对模n的乘法逆元。

（除以一个数再取模=乘以这个数的逆元再取模）

对于同余方程ax ≡ 1（mod n），gcd（a，n）=1的求解就是求解方程ax+ny=1，x，y为整数。这个可用扩展欧几里德算法求出，原同余方程的唯一解就是用扩展欧几里德算法得出的x。

A/B

题目描述

要求（A/B）%9973，但由于A很大，我们只能给出n（n=A%9973）（我们给定的A必能被B整除，且gcd(B,9973)=1）。

输入

数据的第一行是一个T，表示有T组数据。

每组数据有两个数n（0<=n<9973）和B（1<=B<=10^9）。

输出

对呀每组数据输出（A/B）%9973。

输入输出样例

输入：2

? ? ? ? ?1000? 53

? ? ? ? ?87? ?123456789

输出：7922

? ? ? ? ? 6060

n=A%9973即n<9973；gcd(B,9973)=1即B，9973互素。

（A/B）%9973相当于A*B关于9973的逆元；设X为B关于9973的逆元。

题目所求可化为：A*X%9973

代码实现如下：

import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int T=sc.nextInt();
        for(int i=0;i<T;i++){
            int n=sc.nextInt();
            int B=sc.nextInt();
            try{
                ExtGcd.inverseElement(B,9973);
                long x=ExtGcd.x;//x是B的关于9973的逆元
                //x=(x%9973+9973);
                System.out.println(x*n%9973);
            }catch(Exception.e){
                e.printStackTrace();
            }
        }
    }
    private static class ExtGcd{
        static long x;
        static long y;
        /*调用完成后x y是ax+by=gcd（a，b）的解*/
        public static long ext_gcd(long a,long b){
            if(b==0){
                x=1;
                y=0;
                return a;
            }
            long res=ext_gcd(b,a%b);
            long x1=x;
            x=y;
            y=x1-a/b*y;
            return res;
        }
        /**
        *线性方程
        *ax+by=m 当m是gcd（a，b）倍数时有解
        *等价于ax=m mod b
        */
        public static long linearEquation(long a,long b,long m)throws Exception{
            long d=ext_gcd(a,b);
            //m不是gcd（a，b）的倍数，这个方程无解
            if（m%d！=0）throw new Exception（"无解"）；
            long n=m/d;
            x*=n;
            y*=n;
            return d;
        }
        /**
        *求逆元
        *ax = 1 (%mo),gcd(a,mo)=1
        *ax+mo*y=1
        */
        public static long inverseElement(long a,long mo) throws Exception{
            long d=linearEquantion(a,mo,1);//ax+mo*y=1；得到一个最大公约数
            x=(x%mo+mo)%mo;//保证x>0
            return d;
        }
    }

}