算法——数论——同余-Toy模板网

这篇具有很好参考价值的文章主要介绍了算法——数论——同余。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

同余

一、试题算法训练同余方程

同余

同余使人们能够用等式的形式简洁地描述整除关系

同余：若 m（正整数），a 和 b 是整数，a%m==b%m，或(a-b)%m==0，记为 a b(mod m)

求解一元线性同余方程等价于求解二元线性丢番图方程

一元线性同余方程，解法看下面第一题

二元线性丢番图方程 $算法——数论——同余,数据结构与算法（java版）,算法$

逆：的一个解为 a 模 m 的逆

一、试题算法训练同余方程

问题描述

　　求关于x的同余方程ax ≡ 1 (mod b)的最小正整数解。

输入格式

　　输入只有一行，包含两个正整数a, b，用一个空格隔开。

输出格式

　　输出只有一行，包含一个正整数x0，即最小正整数解。输入数据保证一定有解。

样例输入

3 10

样例输出

7

数据规模和约定

　　对于40%的数据，2 ≤b≤ 1,000；
　　对于60%的数据，2 ≤b≤ 50,000,000；
　　对于100%的数据，2 ≤a, b≤ 2,000,000,000。

文章来源地址https://www.toymoban.com/news/detail-829586.html

分析：

这行代码 (x % b + b) % b 的目的是确保最终的结果落在 0 到 b-1 的范围内，即取余操作的结果始终为非负数。

首先，我们知道 % 运算符返回的结果可能是负数，具体取决于被除数和除数的正负性。为了保证结果始终为非负数，我们首先对 x 求模 b，得到一个值在 -b+1 到 b-1 之间的数。然后，我们加上 b，这样就可以确保结果大于等于 0 且小于 2b。最后再次对 b 取模，使结果落在 0 到 b-1 的范围内。

这样的处理方式可以确保得到正确的最小正整数解，同时保证结果在合理的范围内。

package no1_1;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long a = scanner.nextInt();
        long b = scanner.nextInt();
        System.out.println(modInverse(a, b));
    }
    //求a模b的逆，即为同余方程的一个解
    public static long modInverse(long a, long b) {//求逆
        long[] result = new long[2];
        extendGcd(a, b, result);//扩展欧几里得算法求ax+by=1的一个特解result[0]
        long x = result[0];
        return (x % b + b) % b;//保证返回最小正整数
    }

    
    public static long extendGcd(long a, long b, long[] result) {
        if (b == 0) {
            result[0] = 1;
            result[1] = 0;
            return a;
        }
        long[] temp = new long[2];
        long d = extendGcd(b, a % b, temp);
        result[0] = temp[1];
        result[1] = temp[0] - a / b * temp[1];
        return d;
    }
}

到了这里，关于算法——数论——同余的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！