【逆元】HDU-1576
2023-03-14 09:45:17 时间
逆元:
同余方程 ax≡1(mod n),gcd(a,n) = 1 时有解,这时称求出的 x 为 a 的对模n的乘法逆元。(注意:如果gcd(a,n)如果不等于1则无解),解法还是利用扩展欧几里得算法求解方程 ax + ny = 1 求出 x。
1 /** 2 * 求逆元 3 * ax = 1 (% mo),gcd(a,mo)=1 4 * ax+mo*y=1 5 * */ 6 public static long inverseElement(long a, long mo) throws Exception { 7 8 long d = linearEquation(a, mo, 1);//ax+mo*y=1 9 x = (x % mo + mo) % mo;//保证x>0 10 return d; 11 }
题目:HDU-1576
思路:设(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了。
代码:
1 import java.util.Scanner; 2 3 /** 4 * (A/B)%9973,求余,除法不满足交换性,可改为求B关于9973的逆元x, 5 * 这样结果等价于Ax%9973等价于x*A%9973等价于xn%9973, 6 */ 7 8 public class HDU1576 { 9 10 public static void main(String[] args) { 11 Scanner scanner = new Scanner(System.in); 12 int T = scanner.nextInt(); 13 for (int i = 0; i < T; i++) { 14 int n = scanner.nextInt(); 15 int b = scanner.nextInt(); 16 try { 17 MyGcd.inverseElement(b, 9973); 18 long x = MyGcd.x; 19 System.out.println(x*n%9973); 20 } catch (Exception e) { 21 // TODO: handle exception 22 } 23 } 24 } 25 26 private static class MyGcd{ 27 static long x; 28 static long y; 29 30 public static long gcd(long m, long n) { 31 return n == 0 ? m : gcd(n, m % n); 32 } 33 34 public static long ext_gcd(long a,long b){ 35 if (b==0) { 36 x = 1; 37 y = 0; 38 return a; 39 } 40 long res = ext_gcd(b, a % b); 41 long x1 = x; 42 x = y; 43 y = x1 - a / b * y; 44 return res; 45 } 46 47 public static long linearEquation(long a, long b, long m) throws Exception { 48 long d = ext_gcd(a, b); 49 if (m % d != 0) { 50 throw new Exception("无解"); 51 } 52 long n = m / d; 53 x *= n; 54 y *= n; 55 return d; 56 } 57 58 public static long inverseElement(long a, long mo) throws Exception { 59 60 long d = linearEquation(a, mo, 1);// ax+mo*y=1 61 x = (x % mo + mo) % mo;// 保证x>0 62 return d; 63 } 64 } 65 }
结果:
相关文章
- 在 Go 里用 CGO?这 7 个问题你要关注!
- 9款优秀的去中心化通讯软件 Matrix 的客户端
- 求职数据分析,项目经验该怎么写
- 在OKR中,我看到了数据驱动业务的未来
- 火山引擎云原生大数据在金融行业的实践
- OpenHarmony富设备移植指南(二)—从postmarketOS获取移植资源
- 《数据成熟度指数》报告:64%的企业领袖认为大多数员工“不懂数据”
- OpenHarmony 小型系统兼容性测试指南
- 肯睿中国(Cloudera):2023年企业数字战略三大趋势预测
- 适用于 Linux 的十大命令行游戏
- GNOME 截图工具的新旧截图方式
- System76 即将推出的 COSMIC 桌面正在酝酿大变化
- 2GB 内存 8GB 存储即可流畅运行,Windows 11 极致精简版系统 Tiny11 发布
- 迎接 ecode:一个即将推出的具有全新图形用户界面框架的现代、轻量级代码编辑器
- loongarch架构介绍(三)—地址翻译
- Go 语言怎么解决编译器错误“err is shadowed during return”?
- 敏捷:可能被开发人员遗忘的部分
- Denodo预测2023年数据管理和分析的未来
- 利用数据推动可持续发展
- 在 Vue3 中实现 React 原生 Hooks(useState、useEffect),深入理解 React Hooks 的