蓝桥杯刷题5--GCD和LCM

目录

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的性质。
  （1）gcd(a, b) = gcd(a, a+b) = gcd(a, k·a+b)
  （2）gcd(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互素
  （5）gcd(a+cb, 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

最小公倍数LCM（the 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;i<num;i++){arr[i] = scan.nextInt();}Arrays.sort(arr);int min = 0;for(int i = 1;i<num;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])/min+1);scan.close();}public static int gcd(int a ,int b){if(b==0) 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;i<n;i++){int a0 = scan.nextInt();int a1 = scan.nextInt();int b0 = scan.nextInt();int b1 = scan.nextInt();int count = 0;for(int x = 1;x<=Math.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(b==0) 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;i<num;i++){arr[i] = scan.nextLong();}Arrays.sort(arr);long q = Long.MAX_VALUE;long t0 = 0;long t1 = 0;for(int i = 0;i<num-1;i++){if(arr[i+1]!=arr[i] && arr[i+1]/arr[i] < q){q = arr[i+1]/arr[i];t0 = arr[i];t1 = arr[i+1];}}long k = gcd(t0,t1);System.out.println(t1/k + "/" + t0/k);scan.close();}public static long gcd(long a,long b){if(b==0) 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) 当然这里的前提是a<=b; 所以gcd(a+k,b+k)=gcd(a+k,b-a) 这里的a和b都是已知的 我们可以设c=b-a 即c是已知的 所以想要使得a+k与c的最大公因子尽可能地大 因为最大最大能到达c 显然这个式子的最大gcd一定为 c ,我们只需要计算出a 最少需要增加多少可以成为 c 的倍数，这个增量即是答案k