题解：P11600 『Fwb』流星の陨落

pjh0625 · 2025-01-21 19:57:51 · 题解

这是一篇 python 题解：

根据题目描述，我们需要计算最少的流星数量以及此时的流星间隔。题目保证第一个发射流星的位置必须是 1，且流星的发射位置间隔为 k。我们需要确保每一个烟花的位置都会有流星发射。

注意：

1. 计算所有差值的最大公约数：

   • 初始化 k 为第一个差值 w[1]。
   • 遍历数组 w，计算所有差值的最大公约数。

2. 计算最少的流星数量：

   • 使用最后一个烟花的位置 a[n] 除以最大公约数 k，得到基本的流星数量。
   • 如果 a[n] 不能被 k 整除，则需要再增加一颗流星。

import math
import sys

def read():
    x = 0
    f = 1
    ch = sys.stdin.read(1)
    while not ('0' <= ch <= '9'):
        if ch == '-':
            f = -1
        ch = sys.stdin.read(1)
    while '0' <= ch <= '9':
        x = x * 10 + ord(ch) - 48
        ch = sys.stdin.read(1)
    return x * f

n = read()
a = [0] * (n + 1)
kkk = -10**9

for i in range(1, n + 1):
    a[i] = read()
    kkk = max(kkk, a[i])

if n == 1:
    print(2, a[1] - 1)
    sys.exit(0)

w = [0] * n
for i in range(1, n):
    w[i] = a[i + 1] - a[i]

k = w[1]
for i in range(2, n):
    k = math.gcd(k, w[i])

if kkk % k != 0:
    print(kkk // k + 1, k)
else:
    print(kkk // k, k)