题目链接

[蓝桥杯 2019 省 B] 等差数列

题目描述

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

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

输入格式

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

第二行包含 $N$ 个整数 $A_1,A_2,A_3,...,A_N$。（注意 $A_1,A_2,A_3,...,A_N$ 并不一定是按等差数列中的顺序给出 )。

输出格式

输出一个整数表示答案。

输入输出样例

输入

5
2 6 4 10 20

输出

10

提示

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

数据范围

• $2\le N\le 10^5$
• $1\le A_i\le 10^9$

解法：数学

对于一个等差数列，我们要使其项数越少 等价于 让公差$d$ 越大！

对于原数列，我们先将其从小到大排序，得到新数列 a = { a 1 , a 2 , a 3 , . . . , a N } a = \{ a_1,a_2,a_3,...,a_N \} a={a1​,a2​,a3​,...,aN​}。

对于其中任意两项的差值 $x=a_{i+1}-a_i$，都应该是公差 $d$ 的倍数，即 $d|x$，$d$ 能够整除 $x$。

对于所有的这样的差值 $x$，我们要使得 公差$d$ 最大，等价于求其最大公约数 $g$。

对于求出的最大公约数 $g$：

• 如果 $g=0$，说明公差$d=0$，原数列所有元素都相等，故等差数列得长度就等于原数列的元素个数$N$。
• 如果 $g>0$，那么等差数列的长度就为 $1+(a_N-a_1)/g$。

时间复杂度：$O(n)$

C++代码：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
    int n;
    cin>>n;
    
    vector<int> a(n);
    for(int i = 0;i < n;i++) cin>>a[i];
    sort(a.begin(), a.end());
    
    int d = a[n - 1] - a[0], min_d = 0;
    for(int i = 0;i < n - 1;i++) min_d = __gcd(min_d, a[i + 1] - a[i]);
    
    int ans = 0;
    if(min_d) ans = 1 + d / min_d;
    else ans = n;
    
    cout<<ans<<'\n';
    return 0;
}

Java代码：

import java.util.*;
import java.io.*;

public class Main {
	static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	
	public static int gcd(int a, int b) {
		if(b == 0) return a;
		else return gcd(b, a % b);
	}
	
	public static void main(String[] args) throws Exception 
	{
		int n = Integer.parseInt(in.readLine().trim());
		int[] a = new int[n];
		
		String[] str = in.readLine().split(" ");
		for(int i = 0;i < n;i++) a[i] = Integer.parseInt(str[i]);
		
		Arrays.sort(a);
		
		int min_d = 0, d = a[n - 1] - a[0];
		for(int i = 0;i < n - 1;i++) {
			min_d = gcd(min_d, a[i + 1] - a[i]);
		}
		
		int ans = 0;
		if(min_d > 0) ans = 1 + d / min_d;
		else ans = n;
		
		System.out.println(ans);
	}
}