英文题干

After five years, the most high-profile event in motor racing, Formula 1, returns to China. The Chinese Grand Prix was recently held at the Shanghai International Circuit. Formula 1 cars can reach speeds of up to 350 km/h. To ensure the safety of the drivers, the cars must pass rigorous crash tests.

We consider the following simplified version of a crash test. Initially, a car is positioned with its front facing a wall, at a distance of D meters from the wall. This crash test provides n types of boosters, where the i-th type of booster has a thrust performance of hi, and there are ample quantities of each type of booster. Suppose the current distance between the car's front and the wall is d, and we use a booster with a thrust performance of h. When d ≥ h, the car will move forward h meters and then stop. Otherwise, the car will move forward d meters, crash into the wall, and rebound h - d meters, after which it stops, still facing the wall.

Now, you want to know, through any number of operations (including no operation), what the minimum distance between the car's front and the wall can be?

Input:

The first line of input contains two positive integers , denoting the number of boosters and the distance between the Formula 1 car and the wall, respectively.

The second line of inputcontains positive integers , denoting the thrust performance of each booster.

Output:

Output an integer in a line, denoting the minimum possible distance between the car's front and the wall.

中文题干

时隔五年，赛车界最受瞩目的赛事——一级方程式赛车重返中国。中国大奖赛近日在上海国际赛车场举行。一级方程式赛车的速度可达 350 公里/小时。为确保驾驶员的安全，汽车必须通过严格的碰撞测试。

我们考虑以下碰撞测试的简化版本。最初，汽车的前部朝向墙壁，距离墙壁 D 米。该碰撞测试提供了 n 种助推器，其中第 型助推器的推力性能为 ，并且每种类型的助推器都有充足的数量。假设汽车前部和墙壁之间的当前距离为 d，我们使用推力性能为 h 的助推器。当 时，汽车将向前移动 h 米，然后停止。否则，汽车将向前移动 d 米，撞到墙上，然后反弹 米，之后它停下来，仍然面向墙壁。

现在，您想知道，通过任意数量的操作（包括无操作），汽车前部和墙壁之间的最小距离是多少？

思路

一道数学思维题

  1. 我们不妨可以将反弹视作穿墙而过，到达对面的 处。对于任意两种助推器A,B的组合，我们想知道它们如何搭配能达到最优，即求它们能组成的最小步长，从而自然联想到求 gcd！

  2. 接下来就是循环获取各种组合的gcd，如果当中出现 gcd=1 的组合，代表有组合步长为1的方案，直接输出0；否则就继续循环直至求得最小的步长。

  3. 最后用最小步长对 D 取模，并取反弹或不反弹中的最小值即可。

AC代码

时间复杂度：O()

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int infmin = 0xc0c0c0c0;
const int infmax = 0x3f3f3f3f;
const int maxn = 1e2 + 5;

ll h[maxn];
vector<ll> vec;

// GCD
ll gcd(ll a, ll b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    ll D;
    cin >> n >> D;
    for (int i = 1; i <= n; i++) {
        cin >> h[i];
    }

    if (n == 1) {
        vec.push_back(h[1]);
    }
    else {
        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                vec.push_back(gcd(h[i], h[j])); // 用gcd计算所有可以搭配的组合周期
            }
        }
    }
    sort(vec.begin(), vec.end());  // 升序排序

    if (vec[0] == 1) {  // 有每次能步进1的组合，那么最小距离必然为0
        cout << 0;
        return 0;
    }

    for (int i = 0; i < vec.size() - 1; i++) {
        if (vec[i + 1] % vec[i] == 0) {
            vec.erase(vec.begin() + i + 1); // 去重，只保留最小步进因子
            i--;
        }
    }

    while (vec.size() > 1) {
        ll temp = gcd(vec[0], vec[1]);
        if (temp == 1) { // 原理同上
            cout << 0;
            return 0;
        }

        for (int k = 0; k < vec.size(); k++) {
            if (vec[k] % temp == 0) {
                vec.erase(vec.begin() + k);
                k--;
            }
        }
        vec.push_back(temp);
    }

    ll ans = D % vec[0];
    ans = min(ans, vec[0] - ans);
    cout << ans;

    return 0;
}