本文主要是介绍算法——数论——同余,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
目录
同余
一、试题 算法训练 同余方程
同余
- 同余使人们能够用等式的形式简洁地描述整除关系
- 同余:若 m(正整数),a 和 b 是整数,a%m==b%m,或(a-b)%m==0,记为 a b(mod m)
- 求解一元线性同余方程等价于求解二元线性丢番图方程
- 一元线性同余方程 ,解法看下面第一题
- 二元线性丢番图方程
- 逆:的一个解为 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。
分析:
这行代码
(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;}
}
这篇关于算法——数论——同余的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!