wordpress银联插件,深圳网站维护优化,免费ppt模板下载 简约,市场推广计划怎么写目录
1. GCD
1.1 性质
1.2 代码实现
2. LCM
2.1 代码实现
3. 习题
3.1 等差数列
3.2 Hankson的趣味题
3.3 最大比例
3.4 GCD 1. GCD
整数a和b的最大公约数是能同时整除a和b的最大整数#xff0c;记为gcd(a, b)
1.1 性质
GCD有关的题目一般会考核GCD的性质。 …目录
1. GCD
1.1 性质
1.2 代码实现
2. LCM
2.1 代码实现
3. 习题
3.1 等差数列
3.2 Hankson的趣味题
3.3 最大比例
3.4 GCD 1. GCD
整数a和b的最大公约数是能同时整除a和b的最大整数记为gcd(a, b)
1.1 性质
GCD有关的题目一般会考核GCD的性质。 1gcd(a, b) gcd(a, ab) gcd(a, k·ab) 2gcd(ka, kb) k·gcd(a, b) 3多个整数的最大公约数gcd(a, b, c) gcd(gcd(a, b), c) 4若gcd(a, b) d则gcd(a/d, b/d) 1即a/d与b/d互素 5gcd(acb, b) gcd(a, b)
1.2 代码实现
import java.math.BigInteger;
public class Main {public static void main(String[] args) {System.out.println(gcd(45, 9)); // 9System.out.println(gcd(0, 42)); // 42System.out.println(gcd(42, 0)); // 42System.out.println(gcd(0, 0)); // 0System.out.println(gcd(20, 15)); // 5System.out.println(gcd(-20, 15)); // -5System.out.println(gcd(20, -15)); // 5System.out.println(gcd(-20, -15)); // -5System.out.println(gcd(new BigInteger(98938441343232), new BigInteger(33422))); // 2}public static long gcd(long a, long b) {if (b 0) return a; return gcd(b, a % b);}public static BigInteger gcd(BigInteger a, BigInteger b) {return a.gcd(b);}
}2. LCM
最小公倍数LCMthe Least Common Multiple。a和b的最小公倍数lcm(a, b)从算术基本定理推理得到。
2.1 代码实现 public static int gcd(int a, int b) {if (b 0) return a; return gcd(b, a % b);}public static long lcm(int a, int b) {return (long) a / gcd(a, b) * b;}3. 习题
3.1 等差数列 import java.util.*;
public class Main {public static void main(String[] args) {Scanner scan new Scanner(System.in);int num scan.nextInt();int arr[] new int[num];for(int i 0;inum;i){arr[i] scan.nextInt();}Arrays.sort(arr);int min 0;for(int i 1;inum;i){min gcd(min,arr[i] - arr[i-1]);}if(min 0) System.out.println(num);else System.out.println((arr[num-1] - arr[0])/min1);scan.close();}public static int gcd(int a ,int b){if(b0) return a;return gcd(b,a%b);}
} 这是gcd问题。把n个数据排序计算它们的间隔对所有间隔做GCD结果为公差。最少数量等于最大值-最小值/公差1 3.2 Hankson的趣味题 import java.util.*;
public class Main {public static void main(String[] args) {Scanner scan new Scanner(System.in);int n scan.nextInt();for(int i 0;in;i){int a0 scan.nextInt();int a1 scan.nextInt();int b0 scan.nextInt();int b1 scan.nextInt();int count 0;for(int x 1;xMath.sqrt(b1);x){if(b1%x 0){if(gcd(x,a0) a1 lcm(x,b0) b1){count;} int y b1 / x;if (x y){continue; } if (gcd(y, a0) a1 lcm(y, b0) b1){count; }}}System.out.println(count);}scan.close();}public static int gcd(int a,int b){if(b0) return a;return gcd(b,a%b);}public static int lcm(int a,int b){return a/gcd(a,b)*b;}
}
3.3 最大比例 import java.util.*;
public class Main {public static void main(String[] args) {Scanner scan new Scanner(System.in);int num scan.nextInt();long arr[] new long[num];for(int i 0;inum;i){arr[i] scan.nextLong();}Arrays.sort(arr);long q Long.MAX_VALUE;long t0 0;long t1 0;for(int i 0;inum-1;i){if(arr[i1]!arr[i] arr[i1]/arr[i] q){q arr[i1]/arr[i];t0 arr[i];t1 arr[i1];}}long k gcd(t0,t1);System.out.println(t1/k / t0/k);scan.close();}public static long gcd(long a,long b){if(b0) return a;return gcd(b,a%b);}
}
3.4 GCD import java.util.*;
public class Main {public static void main(String[] args) {Scanner scan new Scanner(System.in);long a scan.nextLong();long b scan.nextLong();long c Math.abs(a-b);System.out.println(c - a%c);scan.close();}
} 根据更相减损术可以知道一个等式gcd(a,b)gcd(a,b-a) 当然这里的前提是ab; 所以gcd(ak,bk)gcd(ak,b-a) 这里的a和b都是已知的 我们可以设cb-a 即c是已知的 所以想要使得ak与c的最大公因子尽可能地大 因为最大最大能到达c 显然这个式子的最大gcd一定为 c ,我们只需要计算出a 最少需要增加多少可以成为 c 的倍数这个增量即是答案k
