[HDU]1576:A/B 特殊的同余方程—逆元

逆元

　　同余方程 ax≡1(mod n)，gcd(a,n) = 1 时有解【a,n互为素数】即ax%n=1这时称求出的 x 为 a 的对模n的乘法逆元。自然 ax和1同余

注意：如果gcd(a,n)如果不等于1则无解，解法还是利用扩展欧几里得算法求解方程
ax + ny = 1 求出 x
例如:
ax=13(mod 12) x是关于a%12的逆元

/**
     *ax=1(mod mo),gcd(a,mo)=1;
     * ax=k1*mo+余数
     * 1=k2*mo+余数;
     * a与mo是素数
     */
    public static long inverseElement(long a, long mo) throws Exception {
        long d = LinearEquation(a, mo, 1);//ax+mo*y=1
        x = (x % mo + mo) % mo;//保证x>0
        return d;
    }
//求解线性方程
    static long LinearEquation(long a, long b,long m)throws Exception{
        long d =ext_gcd(a,b);
        if(m%d!=0) throw new Exception("Impossible");
        long t=m/d;
        x*=t;
        y*=t;
        return d;
    }

    private static long ext_gcd(long a, long b) {
        if(b==0) {
            x=1;
            y=0;
            return a;
        }
        long d =ext_gcd(b,a%b);
        long x1=x;
        x=y;
        y=x1-a/b*y;
        return d;
    }

HDU1576

要求(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

S ample Output

7922
6060

思路

思路1

设(A/B)%9973 = k, 则A/B = k + 9973x (x未知），因此A = kB + 9973xB,又A%9973 = n，所以kB%9973 = n, 故kB = n + 9973y (y未知)，故(k/n)B +(-y/n)*9973 = gcd(B,9973) = 1扩展欧几里得求出k/n, 再乘以个n，记得取模，就是answer了。

思路2

n=A%9973，则n=A-A/99739973。又A/B=x，则A=Bx。所以Bx-A/99739973=n。即Bx-9973y=n。
到这里我们可以发现：只要求出x的值，即可算出x%9973，也就是(A/B)%9973了。顺利解决了！
题目关键转到如何求出x了。题目的输入是n和B，利用扩展欧几里德算法可求出gcd(B,9973)=Bx1+9973y1=1的x1。
等式两边同乘以n，得B(nx1)-9973(-ny1)=n。可知nx1就是Bx-9973y=n的解了！！！即x=nx1。

代码

package HDU;

import java.util.Scanner;

public class _1576_ADivideB {
    public static void main(String[] args)throws Exception {
      Scanner cin =new Scanner(System.in);
      long t=cin.nextLong();
        for (long i = 0; i < t; i++) {
            long n=cin.nextLong();
            long B=cin.nextLong();
            inverseElement(B,9973);
            System.out.println((x*n)%9973);
        }
    }
    static long x,y;

    /**
     *ax=1(mod mo),gcd(a,mo)=1;
     * ax=k1*mo+余数
     * 1=k2*mo+余数;
     * a与mo是素数
     */
    public static long inverseElement(long a, long mo) throws Exception {
        long d = LinearEquation(a, mo, 1);//ax+mo*y=1
        x = (x % mo + mo) % mo;//保证x>0 /x就是逆元 逆元是关于模的倒数
        return d;
    }

    static long LinearEquation(long a, long b,long m)throws Exception{
        long d =ext_gcd(a,b);
        if(m%d!=0) throw new Exception("Impossible");
        long t=m/d;
        x*=t;
        y*=t;
        return d;
    }

    private static long ext_gcd(long a, long b) {
        if(b==0) {
            x=1;
            y=0;
            return a;
        }
        long d =ext_gcd(b,a%b);
        long x1=x;
        x=y;
        y=x1-a/b*y;
        return d;
    }
}