gcd

题目大意

你可以选择一个任意长度的子序列 $a_{b_1},a_{b_2},\dots$ 。 然后求得子序列的最大公因数 $g$ 。 将子序列每一个数 $a_{b_i}$变为 $\frac{a_{b_i} \times (g+ 1 )}{g}$。之后对于整个数组求最大公因数是多少。

题解思路

思考一下gcd(x ,x+1) 是多少，答案是 $1$,因此，我们如果选择一个子序列的最大公因数为 $g$ ，那么我们所有因子包含 $g$ 的数都要被选举，否则整个数组最终的 $gcd$ 为 $1$。

因此我们可以枚举自己期望求的最大公因数是多少，之后我们对所有包含期望因子的求 $gcd$,对不包含的数也求另外一组 $gcd$ ，之后进行相应的操作

参考代码

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
using i32 = int32_t;
using i128 = __int128;

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n;
    cin >> n;
    vector<int> arr(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    int maxs = 1;
    for (int i = 1; i <= 5000; i++) {
        int g_1 = 0, g_2 = 0;
        for (int j = 1; j <= n; j++) {
            if (arr[j] % i == 0) g_1 = __gcd(arr[j], g_1);
            else {
                g_2 = __gcd(arr[j], g_2);
            }
        }
        maxs = max(__gcd(g_1 + 1, g_2), maxs);
    }
    cout << maxs << endl;
}