第九题特殊的同余方程-逆元
package 第六章数学问题; import java.util.Scanner; /** * 2022/3/26 * 6.10 特殊的同余方程-逆元 * @author MZFAITHDREAM *模的逆元 *ax=1 *x=1/a *AX=1(% mod) *AX+BY=M * */ public class Test10 { public static void main(String[] args) { // 创建Scanner对象输入内容 Scanner scanner = new Scanner(System.in); int T = scanner.nextInt(); for (int i = 0; i < T; i++) { int n = scanner.nextInt(); int b = scanner.nextInt(); try { MyGcd.inverseElement(b, 9973); long x = MyGcd.x; System.out.println(x*n%9973); } catch (Exception e) { // TODO: handle exception } } } private static class MyGcd{ static long x; static long y; public static long gcd(long m, long n) { return n == 0 ? m : gcd(n, m % n); } public static long ext_gcd(long a,long b){ if (b==0) { x = 1; y = 0; return a; } long res = ext_gcd(b, a % b); long x1 = x; x = y; y = x1 - a / b * y; return res; } public static long linearEquation(long a, long b, long m) throws Exception { long d = ext_gcd(a, b); if (m % d != 0) { throw new Exception("无解"); } long n = m / d; x *= n; y *= n; return d; } public static long inverseElement(long a, long mo) throws Exception { long d = linearEquation(a, mo, 1);// ax+mo*y=1 x = (x % mo + mo) % mo;// 保证x>0 return d; } } }
第十题：很有意思的同余方程组。
package 第六章数学问题; import java.util.ArrayList; import java.util.List; import java.util.Scanner; /** * 6.11 很有意思的同余方程组 * @author MZFAITHDREAM * */ public class Test11 { public static void main(String[] args) throws Exception { Scanner scanner = new Scanner(System.in); int t = 1; List<Long[]> aList = new ArrayList<Long[]>(); List<Long> dList = new ArrayList<Long>(); while(scanner.hasNext()){ Long []a = {scanner.nextLong(),scanner.nextLong(),scanner.nextLong()}; Long d = scanner.nextLong(); if (a[0]==-1&&a[1]==-1&&a[2]==-1&&d==-1) { break; }else { aList.add(a); dList.add(d); } } for (int i = 0; i < aList.size(); i++) { Long[] a = aList.get(i); long d = dList.get(i); Long[] m = { (long) 23, (long) 28, (long) 33 }; long res = MyGcd.linearEquationGroup(a, m); while (res <= d) { res += 21252; } System.out.println("Case " + (t++) + ": the next triple peak occurs in " + (res - d) + " days."); } } private static class MyGcd { static long x; static long y; /** * * * @param a 余数组成的数组 * @param m 模组成的数组 * @return * @throws Exception */ public static long linearEquationGroup(Long[] a, Long[] m) throws Exception { int len = a.length; if (len == 0 && a[0] == 0) return m[0]; for (int i = 1; i < len; i++) { // 这里往前看是两个方程 long a2_a1 = a[i] - a[i - 1]; long d = linearEquation(m[i - 1], -m[i], a2_a1); // 现在的x是y1,用y1求得一个特解 long x0 = a[i - 1] + m[i - 1] * x; long lcm = m[i - 1] * m[i] / d; a[i] = (x0 % lcm + lcm) % lcm;// x0变成正数 m[i] = lcm; } // 合并完之后,只有一个方程 : x = a[len-1] (% m[len-1]) //long d = linearEquation(1, m[len-1], a[len-1]); return a[len - 1] % m[len - 1]; } public static long inverseElement(long a, long mo) throws Exception { long d = linearEquation(a, mo, 1); x = (x % mo + mo) % mo; return d; } public static long linearEquation(long a, long b, long m) throws Exception { long d = ext_gcd(a, b); // m不是gcd(a,b)的倍数,这个方程无解 if (m % d != 0) throw new Exception("无解"); long n = m / d;// 约一下,考虑m是d的倍数 x *= n; y *= n; return d; } public static long ext_gcd(long a, long b) { if (b == 0) { x = 1; y = 0; return a; } long res = ext_gcd(b, a % b); long x1 = x;// 备份x x = y;// 更新x y = x1 - a / b * y;// 更新y return res; } } }
第十一题素数的测试及质因数分解。
package 第六章数学问题; import java.util.HashMap; import java.util.Map; /** * 6.12 素数的测试及质因数分解 * * @author MZFAITHDREAM * */ public class Test12 { /** * @author MZFAITHDREAM * @param args */ public static void main(String[] args) { /** * @author MZFAITHDREAM * * 判断数字是否为素数 */ boolean res = isPrime(7); System.out.println(res); /** * @author MZFAITHDREAM * 质因数分解案例 */ Map<Integer, Integer> map = primeFactor(100); StringBuilder sb = new StringBuilder(); for(Map.Entry<Integer, Integer> entry:map.entrySet()){ int k = entry.getKey(); int v = entry.getValue(); for (int i = 0; i < v; i++) { sb.append("*"+k); } } System.out.println(map); System.out.println(sb.substring(1)); } /** * @author MZFAITHDREAM * 检查num是不是素数 * 2~根号n */ public static boolean isPrime(long num){ for (int i = 2; i*i <= num; i++) { if (num%i==0) { return false; } } return true; } /** * 质因素分解：100 = 2*2*5*5 * map是质因数-出现次数的映射 */ public static Map<Integer, Integer> primeFactor(int num){ Map<Integer, Integer> map = new HashMap<>(); for (int i = 2; i*i <= num; i++) { while(num%i==0){ Integer v = map.get(i); if (v==null) { map.put(i, 1); }else { map.put(i, v+1); } num /= i; } } return map; } }
第十二题素数的筛法
package 第六章数学问题; import java.math.BigInteger; /** * 6.13 素数的筛法 * @author MZFAITHDREAM * */ public class Test15 { public static void main(String[] args) { long now = System.currentTimeMillis(); f(100002); System.out.println("耗时：" + (System.currentTimeMillis() - now) + "ms"); now = System.currentTimeMillis(); BigInteger bigInteger = new BigInteger("1"); for (int i = 1; i <= 100002; i++) { bigInteger = bigInteger.nextProbablePrime(); } System.out.println(bigInteger); System.out.println("耗时：" + (System.currentTimeMillis() - now) + "ms"); now = System.currentTimeMillis(); int count = 0; long x = 2; while(count<100002){ if (isPrime(x)) { count++; } x++; } System.out.println(x-1); System.out.println("耗时：" + (System.currentTimeMillis() - now) + "ms"); } /** * * @param num * @return */ public static boolean isPrime(long num){ for (int i = 2; i*i <= num; i++) { if (num%i==0) { return false; } } return true; } /** * * @param N 第N个素 */ private static void f(int N){ int n = 2; while(n/Math.log(n)<N){ n++; } int []arr = new int[n]; int x = 2; while(x<n){ if (arr[x]!=0) { x++; continue; } int k=2; while(x*k<n){ arr[x*k] = -1; k++; } x++; } int sum = 0; for (int i = 2; i < arr.length; i++) { // 是素数，计数+1 if (arr[i] == 0) { // System.out.println(i); sum++; } if (sum == N) { System.out.println(i); return; } } } }
第十三题快速幂运算
package 第六章数学问题; /** * 6.14 快速幂运算 * * @author MZFAITHDREAM * */ public class Test16 { public static void main(String[] args) { System.out.println(ex2(2, 9)); } /** * * @param a * @param n * @return */ public static int ex(int a,int n){ if(n==0)return 1; if(n==1)return a; int temp = a; // a的1次方 int res = 1; int exponent = 1; while((exponent<<1)<n){ temp = temp * temp; exponent = exponent << 1; } res *= ex(a,n-exponent); return res * temp; } /** * 快速幂 O(lgn) */ public static long ex2(long n,long m){ if(n==0) return 1; long pingFangShu = n; // n 的 1 次方 long result = 1; while (m != 0) { // 遇1累乘现在的幂 if ((m & 1) == 1) result *= pingFangShu; // 每移位一次，幂累乘方一次 pingFangShu = pingFangShu * pingFangShu; // 右移一位 m >>= 1; } return result; } }
