当前位置: 首页 > article >正文

算法基础-扩展欧几里得算法

扩展欧几里得

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        while (n-- > 0) {
            int a = in.nextInt();
            int b = in.nextInt();
            int[] m = exgcd(a, b);
            System.out.println(m[0] + " " + m[1]);
        }
    }
    private static int[] exgcd(int a, int b) {
        if (b == 0)
            return new int[]{1, 0};
        int[] result = exgcd(b, a % b);
        int x = result[0];
        int y = result[1];
        result[0] = y;
        result[1] = x - (a / b) * y;
        return result;
    }
}

线性同余方程

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        while (n-- > 0) {
            int a = in.nextInt();
            int b = in.nextInt();
            int m = in.nextInt();
            int[] r = exgcd(a, m);
            if(b % r[2] != 0) {
                System.out.println("impossible");
            } else {
                System.out.println(r[0] * ((long) b / r[2]) % m);
            }
        }
    }

    private static int[] exgcd(int a, int m) {
        if (m == 0)
            return new int[]{1, 0, a};
        int[] result = exgcd(m, a % m);
        int x = result[0];
        int y = result[1];
        result[0] = y;
        result[1] = x - (a / m) * y;
        return result;
    }
}


http://www.kler.cn/news/304178.html

相关文章:

  • Python知识点:如何使用Python进行Excel文件操作(OpenPyXL、Pandas)
  • 源码到class字节码的编译流程 字节码到内存的Java类加载流程
  • 【一分钟学C++】std::memory_order
  • Vue3+Django5+REST Framework开发电脑管理系统
  • 【计算机网络 - 基础问题】每日 3 题(一)
  • 程序的结构和控制流与数据流
  • MySQL 表的增删改查
  • 注解(Java程序的一种特殊“注释”,用于工具处理的标注)
  • 每日一问:C++ 中重写和重载的区别
  • vue3 5个常用的API
  • SpringBoot开发——整合Spring Data MongoDB
  • [数据集][目标检测]车油口挡板开关闭合检测数据集VOC+YOLO格式138张2类别
  • 凸优化学习(2)——梯度类方法求解(gradient descent)
  • 构建有温度的用户关系:开源 AI 智能名片、链动 2+1 模式与 S2B2C 商城小程序的作用
  • 华为SMU02B1管理模块WEB登录与账户密码信息
  • HTB-Archetype(winPEAS枚举工具,mssql xp_cmdshell)
  • Linux - make/Makefile工具的基础使用
  • Java的发展史与前景
  • 贪吃蛇项目实现(C语言)——附源码
  • JavaScript知识点3
  • JMeter脚本开发
  • 人工智能领域的性能指的是什么
  • Unity3D类似于桌面精灵的功能实现
  • JDK 17 微服务启动JVM参数调优实战
  • 自学前端靠谱吗?
  • onRequestPermissionsResult详解
  • 多账号注册脚本不会被平台监控吗
  • 写论文还在卡壳?教你用ChatGPT轻松搞定过渡段落!
  • Google大数据架构技术栈
  • 91-java cms垃圾回收器