解题思路

题目要求我们计算钟响声的最大可能周期。根据题意，钟应该有一个固定的周期 $T$，即时钟会在时间点 $0, T, 2T, 3T, \ldots$ 上响起。由于钟老化，漏掉了某些本应响起的时间点。我们已知实际的响声时间序列，目标是计算出最大可能的周期 $T$，使得这个周期能够涵盖这些响声时间点，并且符合钟的规律。

思路分析

1. 相邻时间差的计算： 观察时间点之间的差值。设定 $\Delta_i = a_{i+1} - a_i$，其中 $i$ 是时间点的下标，计算所有相邻时间点之间的差值。为了找到最大周期 $T$，该周期必须能够整除这些时间差。

2. 最大公约数（GCD）： 因为周期 $T$ 必须能够整除每一对相邻时间点的差值，问题可以转化为：在这些差值中找出最大公约数。最大公约数即为这些时间差的最大公倍数，也就是我们要求的最大周期。

3. 算法步骤：

   • 计算相邻时间点之间的差值。
   • 计算这些差值的最大公约数（GCD）。
   • 输出最大公约数作为周期 $T$。

4. 时间复杂度： 计算相邻时间差的时间复杂度为 $O(n)$。计算多个数的 GCD 时间复杂度为 $O(\log(\text{数值范围}))$。由于需要计算所有时间差的 GCD，因此整体复杂度为 $O(n \log(\text{最大差值}))$。

代码实现

Python代码

import math

def main():
    # 读取输入
    n = int(input())  # 响声次数
    a = list(map(int, input().split()))  # 时间点列表
    
    # 计算相邻时间点之间的差值
    diffs = [a[i+1] - a[i] for i in range(n-1)]
    
    # 计算这些差值的最大公约数
    gcd_value = diffs[0]
    for diff in diffs[1:]:
        gcd_value = math.gcd(gcd_value, diff)
    
    # 输出最大公约数作为最大周期
    print(gcd_value)

if __name__ == '__main__':
    main()

Java代码

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        // 读取输入
        int n = Integer.parseInt(br.readLine());
        String[] input = br.readLine().split(" ");
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(input[i]);
        }
        
        // 计算相邻时间点的差值
        int gcd_value = a[1] - a[0];
        for (int i = 1; i < n - 1; i++) {
            gcd_value = gcd(gcd_value, a[i + 1] - a[i]);
        }
        
        // 输出最大公约数作为最大周期
        System.out.println(gcd_value);
    }

    // 计算最大公约数
    public static int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}

C++代码

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

int main() {
    int n;
    cin >> n;
    
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    
    // 计算相邻时间点的差值
    int gcd_value = a[1] - a[0];
    for (int i = 1; i < n - 1; ++i) {
        gcd_value = gcd(gcd_value, a[i + 1] - a[i]);
    }
    
    // 输出最大公约数作为最大周期
    cout << gcd_value << endl;

    return 0;
}

题目内容

笨蛋同学家里有一只废弃已久的钟，某天它突然开始断断续续地响起来。由于内部机件老化，时常漏掉本应响起的声音。给定它实际发出响声的时间点，笨蛋同学想知道这口钟响声的 最大可能周期 是多少？更正式地，记一只正常的时钟会以一个固定的 整数 周期 $T$ 响起(即在整数时间点 $0,T,2T,3T,...$ 响起)，但这只钟由于内部机件老化，时常会漏掉本应响起的声音，现在给定它实际发出响声的一系列时间点，笨蛋同学想知道这口钟本应有的最大可能周期 $T$ 是多少？

输入描述

第一行输入一个整数 $n(2 ≦n≦2×10^5)$ ，表示钟一共响了 $n$ 下；

第二行输入 $n$ 个整数 $a_0,a_1,...,a_{n-1}(0 ≦a_i≦10^9)$ ，表示每次响声的时间点。保证 $a_0= 0$ ，且序列严格单调递增。

输出描述

输出一个整数，表示钟响声的 最大可能周期 。

样例1

输入

3
0 1 3

输出

1

说明

在这个样例中，观测到的相邻响声时间差为 $1-0=1$ 和 $3-1=2$ 。我们可以找到，原本最大可能周期为 $1$ 。可以很显然的证明，若周期为 $1$ ，那么钟会在时间点 $0,1,2,3,...$ 响起，符合样例中提到的数据(时间点 $2$ 漏掉了一声)。