P11600 『Fwb』流星の陨落

题目描述

流星雨来了！

当然，这场流星雨确确实实是 Fwb 设计的。Fwb 在天空中放置了许多的流星，同时也在地面上放置了许多的烟花。当流星和烟花发生碰撞时，就会出现美丽而独特的风景。

由于方便控制流星雨的发射，流星的发射是有规律的，这个发射的规律叫做流星间隔。我们把地面上烟花的摆放看作一个数轴，若流星间隔是 $k$，那么在 $i$ 位置发射一颗流星后，下一个发射流星的位置必须是 $i+k$。特殊的，第一个发射流星的位置必须是 $1$。

为了使流星雨好看，保证每一个烟花都会和流星碰撞，即每一个烟花的位置都会有流星发射。但不保证每一个流星都有可碰撞的烟花。为了尽可能减少资源消耗，发射的流星应在满足条件的前提下最少，现在想请你算出，发射的流星雨中最少有多少颗流星以及此时的流星间隔是多少。

输入格式

输入的第一行包含一个正整数 $n$，代表地上共放置了 $n$ 个烟花。

第二行共 $n$ 个正整数，代表烟花在数轴上的位置 $a_i$（保证 $a_i$ 递增）。默认最后一个烟花的位置为数轴的尽头，即保证在位置 $i$（$i>a_n$）不会再有流星发射。

输出格式

输出共一行，包含两个正整数，分别表示流星雨中最少的流星数量以及此时的流星间隔。

输入输出样例 #1

输入 #1

5
1 3 5 7 9

输出 #1

5 2

输入输出样例 #2

输入 #2

7
10 13 19 301 304 307 3004

输出 #2

1002 3

输入输出样例 #3

输入 #3

3
2 1000000 1234567

输出 #3

1234567 1

说明/提示

【样例 1 解释】

当流星间隔为 $2$ 时，流星会发射在 $[1,3,5,7,9]$ 的位置，恰好覆盖所有的烟花。此时发射的流星数量最少为 $5$。

【数据范围】

对于所有的测试数据，保证：

• $1\le n\le 10^5$。
• 对于任意的 $i$（$1\le i\le n$），都有 $1\le a_i\le 10^9$。

测试点	$n=$	$a_i\le$	特殊性质
$1$	$1$	$10$	无
$2$	$10^5$	$10^9$	A
$3,4$	$10^5$	$10^9$	B
$5,6,7$	$10$	$10^9$	C
$8,9,10$	$10^5$	$10^9$	无

特殊性质 A：保证 $a_i=a_{i-1}+1$（$1<i\le n$）。

特殊性质 B：保证 $a_i-a_{i-1}=a_{i+1}-a_i$（$1<i<n$）。

特殊性质 C：保证至少出现一次 $a_i-a_{i-1}\le 10^4$（$2\le i\le n$）。

题目保证不出现 $n=1$ 且 $a_1=1$ 的情况。

C++实现

#include <bits/stdc++.h>
using namespace std;
int n, m, mx;
int main()
{
cin >> n >> m;
mx = --m;
for(int i = 2, x; i <= n; i++)
{
scanf(“%d”, &x);
m = __gcd(m, (x - 1));
mx = max(mx, (x - 1));
}
cout << mx / m + 1 << " " << m;
return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容