做灯饰的企业都会在哪些网站,织梦网站seo,生成拼贴的网站,企业门户管理系统目录
同余
一、试题 算法训练 同余方程 同余 同余使人们能够用等式的形式简洁地描述整除关系同余#xff1a;若 m#xff08;正整数#xff09;#xff0c;a 和 b 是整数#xff0c;a%mb%m#xff0c;或(a-b)%m0#xff0c;记为 a b(mod m)求解一元线性同余方程等价于…目录
同余
一、试题 算法训练 同余方程 同余 同余使人们能够用等式的形式简洁地描述整除关系同余若 m正整数a 和 b 是整数a%mb%m或(a-b)%m0记为 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得到一个值在 -b1 到 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);//扩展欧几里得算法求axby1的一个特解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;}
}
