首页 > 编程学习 > [蓝桥杯2019初赛]等差数列,数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一部分的数列,只记得其中N 个整数。 现在给出这N 个整数,小明想知道包含这N 个整数的最短的等差数列有几

[蓝桥杯2019初赛]等差数列java简单方法。完美AC

题目描述
数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一部分的数列,只记得其中N 个整数。
现在给出这N 个整数,小明想知道包含这N 个整数的最短的等差数列有几项?
输入
输入的第一行包含一个整数N。
第二行包含N 个整数A1.A2,…, AN。(注意A1<=AN 并不一定是按等差数列中的顺序给出)
2<=N<=100000,0<=Ai<=10^9
输出
输出一个整数表示答案。
样例输入 Copy
5
2 6 4 10 20
样例输出 Copy
10
提示
包含2、6、4、10、20 的最短的等差数列是2、4、6、8、10、12、14、16、18、20。

注意:
每一项与第一项的差一定是d的倍数(所以所有项的最大公约数)
当d != 0 时, (a末 - a初) / d + 1 ---- 让公差d最大即可
当d == 0 时,答案为 n

AC代码:

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static long diff;
    public static void main(String[] args) {

        Scanner scanner=new Scanner(System.in);
        int n=scanner.nextInt();
        int arr[]=new int[n];
        for (int i = 0; i < n; i++) {
            arr[i]=scanner.nextInt();
        }
        Arrays.sort(arr);

        int diff=0;
        for (int i = 0; i <n-1; i++) {
         diff=gcd(diff,arr[i+1]-arr[i]);
        }

        if (diff==0){
            System.out.println(n);
        }
        else {
            long count=0;
            System.out.println((arr[n-1]-arr[0])/diff+1);
        }
    }
    public static int gcd(int a,int b) {//欧几里得算法(辗转相除法)
        return b!=0?gcd(b, a%b):a;//求两个正整数的最大公约数
    }

}

在这里插入图片描述

在这里插入图片描述
原创不易,点个赞吧!

Copyright © 2010-2022 ngui.cc 版权所有 |关于我们| 联系方式| 豫B2-20100000