逆元
同余方程 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;
}
}
参考文献
[2] 题目 https://cn.vjudge.net/problem/HDU-1576
本文地址:https://dxoca.cn/Algorithm/194.html 百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。