寒光博客

[HDU]1576:A/B 特殊的同余方程—逆元
逆元   同余方程 ax≡1(mod n),gcd(a,n) = 1 时有解【a,n互为素数】即ax%n=1这时称...
扫描右侧二维码阅读全文
27
2019/07

[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;
    }
}

参考文献

本文作者:Author:     文章标题:[HDU]1576:A/B 特殊的同余方程—逆元
本文地址:https://dxoca.cn/Algorithm/194.html       百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。
Last modification:July 31st, 2019 at 12:15 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment