数论大合集 P10183 Running | LQOJ97 K倍区间

P10183

题目描述

小 Z 在一条公路上跑步，公路上有 n 个超市，第 i 个超市的位置为 ai。当小 Z 经过一个超市的时间为奇数时，他就会去逛超市，从而被同学拉爆。

小 Z 最开始位于位置为 0 的点。他会在每个单位时间向右跑 v 个单位长度。

请求出：能够使小 Z 经过 n 个超市中每一个超市时，都不去逛超市的 v 的最大值。

规定 v 必须是正整数，且小 Z 到达任意一个超市时，花费的时间必须为整数，换言之，你需要保证小 Z 到达任意一个超市的时间都是偶数。注意时间初始为 0。

输入格式

输入共 n+1 行。
第 1 行，1 个正整数 n。
第 2∼n+1 行，每行 1 个正整数，第 i+1 行输入的正整数是 a i

输入输出样例

输入#1

2
1
2

输出#1

-1

输入#2

5
10
20
30
40
50

输出#2

5

题解

gcd没跑的。最后结果除以2，我的理解是到最后如果最大公因数还是奇数的话，是一定有奇数时间走到倒霉的超市的，偶数时除以2以确保每个超市到达的时间都是偶数时间（以最大公因数来说，第一个奇数时间就会到达第一个超市）。

代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define akitama return 0
#define ll long long
#define endl '\n'

vector<ll> mod;

ll _gcd(int n, int m) {
    if (n % m == 0) return m;
    else return _gcd(m, n % m); 
}

void solve() {
    int n; cin >> n;
    vector<ll> a(n);
    ll ans = -1;
    for (int i = 0; i < n; ++ i) {
        cin >> a[i];
        if (i == 0) ans = a[i];
        else ans = _gcd(ans, a[i]);
    }
    if (ans % 2 == 1) cout << "-1" << endl;
    else cout << ans / 2 << endl;
}

signed main() {
    cin.tie(nullptr)->ios::sync_with_stdio(false);
    solve();
    akitama;
}