题目描述

间接考察最大公约数

每一项与第一项的差一定是d的倍数 每一次去做差和d 找最大公约数 这时候等差数列最短

当d ！= 0 时， 项数 = (a末 - a初) / d + 1
当d == 0 时， 项数 = n

样例

import java.util.*;
/*
   每一项与第一项的差一定是d的倍数 每一次去做差和d 找最大公约数  这时候等差数列最短

   当d ！= 0 时， 项数 = (a末 - a初) / d  + 1
   当d  == 0 时， 项数 = n 
*/

public class Main {

    // 求最大公约数
    public static int gcd(int a, int b) {
        return b != 0 ? gcd(b, a % b) : a;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();

        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }

        Arrays.sort(a);

        // 求后面各项与第一项所有差值的最大公约数
        int d = 0;
        for (int i = 1; i < n; i++) {
            d = gcd(d, a[i] - a[0]);
        }

        if (d == 0) {
            System.out.println(n);
        } else {
            System.out.println((a[n - 1] - a[0]) / d + 1);
        }
    }
}