【蓝桥杯】历届真题 等差数列（省赛）Java

【资源限制】

内存限制：256.0MB   C/C++时间限制：1.0s   Java时间限制：3.0s   Python时间限制：5.0s

【问题描述】

        数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一部分的数列，只记得其中N个整数。

        现在给出这N个整数，小明想知道包含这N个整数的最短的等差数列有几项?

【输入格式】

        输入的第一行包含一个整数N。

        第二行包含N个整数A1,A2,.… ,AN。(注意Ai~Ax并不一定是按等差数列中的顺序给出)

【输出格式】

        输出一个整数表示答案。

【样例输入】

5

2 6 4 10 20

【样例输出】

10

【样例说明】

        包含2、6、4、10、20的最短的等差数列是2、4、6、8、10、12、14、16、18、20。

【评测用例规模与约定】

        对于所有评测用例，2≤N ≤ 100000，0≤A; ≤ 10^9。

【思路与分析】

        求最大的等差数列，说白了也就是求最大数和最小数之间的最大公约数。根据题意已知：所给元素顺序并不一定是按等差数列中的顺序给出。因此，最先进行的操作是对于获取的数组元素进行排序。

        而后根据等差数列的求和公式（an=a1+(n-1)*d）的变式（n= (an-a1)/d+1）进行计算。

【代码】

/*
输入的第一行包含一个整数N。
第二行包含N个整数A1,A2,…  ,AN。
(注意Ai~Ax并不一定是按等差数列中的顺序给出)
*/
import java.util.Arrays;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc=new Scanner(System.in);int n=sc.nextInt();int[] arr=new int[n];for(int i=0;i<n;i++){arr[i]=sc.nextInt();}Arrays.sort(arr);int m=0;for(int i=0;i<arr.length-1;i++){m=temp(m,arr[i+1]-arr[i]);}//项数为0直接输出公约数if(m==0){System.out.println(n);} else {long num=0;System.out.println((arr[n-1]-arr[0])/m+1);}}//利用三元运算求两个正整数的最大公约数public static int temp(int a,int b){return b!=0?temp(b,a%b):a;}
}