#include <bits/stdc++.h>
#define int long long
 
using namespace std;
 
const int INF = (int) 1e18;
 
int32_t main() {
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int _;
    cin >> _;
 
    while (_--) {
        int n;
        cin >> n;
 
        vector <int> a(n);
        int mx = -INF;
        int mn = INF;
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
            mx = max(mx, a[i]);
            mn = min(mn, a[i]);
        }
 
        cout << mx - mn + 1 << "\n";
    }
 
    return 0;
}

Попробуйте найти свойство, которое не изменяется при проведении операций.

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, k; cin >> n >> k;
        string s; cin >> s;
        vector<int> cnt(k, 0);
        for (int i = 0; i < n; i++) cnt[i % k] += s[i] - '0';
        bool ok = true;
        for (int r = 0; r < k; r++) {
            if (cnt[r] % 2) {
                ok = false;
                break;
            }
        }
        cout << (ok ? "YES" : "NO") << '\n';
    }
}

Можно показать, что выгодно сначала делать только деления, а потом только прибавления.

#include <bits/stdc++.h>
#define int long long
 
using namespace std;
 
const int INF = (int) 1e18;
 
int32_t main() {
    int _;
    cin >> _;
 
    while (_--) {
        int a, b, x;
        cin >> a >> b >> x;
 
        int ans = INF;
        int i = 0;
        while (a != b) {
            if (b > a) {
                swap(a, b);
            }
 
            ans = min(ans, abs(a - b) + i);
            a /= x;
            i++;
        }
 
        ans = min(ans, i);
 
        cout << ans << "\n";
    }
 
    return 0;
}

Что произойдёт, если Арсений первым ходом выберет максимум массива?

Попробуйте посмотреть на второй максимум

#include <bits/stdc++.h>

using namespace std;
void solve();

int main() {
    int t; cin >> t;
    while (t--) solve();
    return 0;
}

void solve() {
    int n, k; cin >> n >> k;
    vector<int> A(n);
    for (auto& x : A) cin >> x;
    sort(A.begin(), A.end());
    vector<pair<int, int>> a = {{A[0], 1}};
    for (int i = 1; i < n; ++i) {
        if (A[i] == A[i - 1]) a.back().second++;
        else a.emplace_back(A[i], 1);
    }

    while (a.size() > 0) {
        n = a.size();
        if (a[n - 1].second % 2 == 0) {
            cout << "YES\n";
            return;
        }
        if (n == 1) {
            cout << "NO\n";
            return;
        }
        if (a[n - 1].first - a[n - 2].first <= k) {
            cout << "YES\n";
            return;
        }
        a.pop_back();
    }
}

Отрезки массива не нужно проверять на непересечение.

#include <bits/stdc++.h>

using namespace std;
void solve();

int main() {
    int t = 1; cin >> t;
    while (t--) solve();
    return 0;
}

void solve() {
    int n; cin >> n;
    vector<int> a(n);
    for (auto& x : a) cin >> x, --x;
    vector<vector<bool>> able(n, vector<bool>(n));
    for (int i = 0; i < n; ++i) {
        vector<int> us(n);
        int mn = a[i], mx = a[i];
        for (int j = i; j < n; ++j) {
            if (us[a[j]]) break;
            us[a[j]] = 1;
            mn = min(mn, a[j]), mx = max(mx, a[j]);
            if (mx - mn == j - i) able[mn][mx] = 1;
        }
    }
    
    for (int ans = n; ans > 0; --ans) {
        for (int i = 0; i + 2 * ans <= n; ++i) {
            if (able[i][i + ans - 1] && able[i + ans][i + 2 * ans - 1]) {
                cout << ans << '\n';
                return;
            }
        }
    }
    cout << "0\n";
}

Что можно сказать про $$$gcd(p_i, p_j)$$$ для любой пары $$$(i, j)$$$?

Возьмем какое то простое число $$$pr$$$. Сколько элементов массива p может быть кратно этому $$$pr$$$?

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <bits/stdc++.h>
#include <immintrin.h>
 
using namespace __gnu_pbds;
using namespace std;
 
#define eps 1e-7
#define MOD2 119 * (1ll << 23) + 1
#define int long long
#define mp make_pair
#define pll pair <long long, long long>
#define next return
#define skip continue
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define f first
#define max_of max_element
#define min_of min_element
#define s second
 
// const int MAX_MEM = 4e8;
// int mpos = 0;
// alignas(long long) char mem[MAX_MEM];
// inline void * operator new(size_t n) {
//     if (n & 7) n += 8 - (n & 7);
//     char *res = mem + mpos;
//     mpos += n;
//     return (void *)res;
// }
// void operator delete(void *) {}
 
int scan() {
    int x;
    cin >> x;
    return x;
}
 
string read() {
    string s;
    cin >> s;
    return s;
}
 
const int N = 1e6 + 5, MOD = 1e9 + 7;
int lp[N], a[N], x, n, v[101];
vector<int> pr, divs[N];
 
int bin_pow(int x, int n) {
    int res = 1;
    while (n) {
        if ((n & 1)) res = res * x % MOD;
        n >>= 1;
        x = x * x % MOD;
    }
    return res;
}
 
int solveF1_AUTHOR() {
    map <int, int> cnt;
    int cur_x;
    int mx = *max_element(a + 1, a + n + 1);
    set <int> setik;
    for (int i = 1; i <= n; i++) {
        int val = a[i];
        cur_x = val;
        while (cur_x > 1) {
            setik.insert(lp[cur_x]);
            cnt[lp[cur_x]]++;
            cur_x /= lp[cur_x];
        }
    }
    int ans = 1;
    for (auto prime: setik) {
        int sum = 1;
        //cout << prime << ' ' << cnt[prime] << '\n';
        ans = (ans * (cnt[prime] + 1)) % MOD;
    }
    return ans;
}
 
 
int32_t main() {
    lp[1] = 1;
    for (int i = 2; i < N; i++) {
        if (lp[i] == 0) {
            pr.push_back(i);
            lp[i] = i;
        }
        for (int j = 0; j < (int) pr.size() && pr[j] <= lp[i] && i * pr[j] < N; j++) {
            lp[i * pr[j]] = pr[j];
        }
    }
    int t = scan();
    while (t--) {
        n = scan(); x = scan();
        for (int i = 1; i <= n; i++) a[i] = scan();
        cout << solveF1_AUTHOR() << '\n';
    }
}

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <bits/stdc++.h>
#include <immintrin.h>

using namespace __gnu_pbds;
using namespace std;

#define eps 1e-7
#define MOD2 119 * (1ll << 23) + 1
#define int long long
#define mp make_pair
#define pll pair <long long, long long>
#define next return
#define skip continue
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define f first
#define max_of max_element
#define min_of min_element
#define s second

int scan() {
    int x;
    cin >> x;
    return x;
}

string read() {
    string s;
    cin >> s;
    return s;
}

const int N = 1e6 + 2, MOD = 1e9 + 7;
int lp[N], a[N], x, n, v[N];
vector<int> pr, divs[N];

int MAX_V = -1E9;

int solve_for_prime(int vp) {
    int mx_pref = 0;
    int S = 0;
    for (int i = 1; i <= n; i++) S += v[i];
    S = min(S, 36ll);
    int dp[MAX_V + 1][MAX_V + S + 2];
    int old_pref_sum[MAX_V + 1][MAX_V + S + 2];
    int old_pref_sum2[MAX_V + 1][MAX_V + S + 2];
    memset(dp, 0, sizeof dp);
    memset(old_pref_sum, 0, sizeof old_pref_sum);
    memset(old_pref_sum2, 0, sizeof old_pref_sum2);
    int sum = 0;
    dp[0][0] = 1;
    for (int i = 0; i <= n; i++) {
        for (int sum_vp = 0; sum_vp <= S && i > 0; sum_vp++) {
            for (int new_max = 1; new_max <= min(sum_vp, v[i]); new_max++) {
                dp[new_max][sum_vp] += old_pref_sum2[new_max - 1][sum_vp - new_max];
                if (dp[new_max][sum_vp] >= MOD) dp[new_max][sum_vp] -= MOD;
            }
            for (int old_max = 0; old_max <= min(mx_pref, sum_vp); old_max++) {
                dp[old_max][sum_vp] += (old_pref_sum[old_max][sum_vp] + MOD - (sum_vp - min(old_max, v[i]) - 1 < 0 ? 0 :
                                                                              old_pref_sum[old_max][sum_vp - min(old_max, v[i]) - 1])) % MOD;
                //if (dp[old_max][sum_vp] >= MOD) dp[old_max][sum_vp] -= MOD;

            }
        }
        for (int old_max = 0; old_max <= MAX_V; old_max++) {
            for (int j = 0; j <= MAX_V + S; j++) {
                old_pref_sum[old_max][j] = 0;
                old_pref_sum[old_max][j] = (!j ? dp[old_max][j] : old_pref_sum[old_max][j - 1] + dp[old_max][j]);
                if (old_pref_sum[old_max][j] >= MOD) old_pref_sum[old_max][j] -= MOD;
            }
        }
        for (int j = 0; j <= MAX_V + S; j++) {
            for (int old_max = 0; old_max <= MAX_V; old_max++) {
                old_pref_sum2[old_max][j] = 0;
                old_pref_sum2[old_max][j] = (!old_max ? dp[old_max][j] : old_pref_sum2[old_max - 1][j] + dp[old_max][j]);
                if (old_pref_sum2[old_max][j] >= MOD) old_pref_sum2[old_max][j] -= MOD;
                if(i != n) dp[old_max][j] = 0;
            }
        }
        mx_pref = max(mx_pref, v[i]);
    }
    int ret = 0;
    for (int mx = 1; vp + mx <= S && mx <= MAX_V; mx++) {
        ret = (ret + dp[mx][vp + mx]);
        if (ret >= MOD) ret -= MOD;
    }
    return ret;
}

int solveF2_AUTHOR() {
    map<int, int> cnt_pr;
    int cur_x = x;
    while (cur_x > 1) {
        int next_div = lp[cur_x];
        cnt_pr[next_div]++;
        cur_x /= next_div;
    }
    int ans = 1;
    for (auto [prime, cnt]: cnt_pr) {
        MAX_V = -1e9;
        for (int i = 1; i <= n; i++) {
            cur_x = a[i];
            v[i] = 0;
            while (cur_x % prime == 0) {
                v[i]++;
                cur_x /= prime;
            }
            MAX_V = max(MAX_V, v[i]);
        }
        ans = (ans * solve_for_prime(cnt)) % MOD;
    }
    map <int, int> cnt;
    int mx = *max_element(a + 1, a + n + 1);
    set <int> setik;
    for (int i = 1; i <= n; i++) {
        int val = a[i];
        cur_x = val;
        while (cur_x > 1) {
            cnt[lp[cur_x]]++;
            setik.insert(lp[cur_x]);
            cur_x /= lp[cur_x];
        }
    }
    for (auto prime: setik) {
        //if (2 * prime > mx) break;
        int sum = 1;
        if (x % prime != 0) ans = (ans * (cnt[prime] + 1)) % MOD;
    }
    return ans;
}


int32_t main() {
    for (int i = 2; i < N; i++) {
        if (lp[i] == 0) {
            pr.push_back(i);
            lp[i] = i;
        }
        for (int j = 0; j < (int) pr.size() && pr[j] <= lp[i] && i * pr[j] < N; j++) {
            lp[i * pr[j]] = pr[j];
        }
    }
    int t = scan();
    while (t--) {
        n = scan(), x = scan();
        for (int i = 1; i <= n; i++) a[i] = scan();
        cout << solveF2_AUTHOR() << '\n';
    }
}

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("O3,unroll-loops")

#include <bits/stdc++.h>
#include <experimental/random>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

using ll = long long;
using ld = long double;
using ordered_set = tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>;
using str = string;
const ll INF = 1e18, MOD = 1e9 + 7;
template<class T> using pq_min = priority_queue<T, vector<T>, greater<T>>;
template<class T> using pq_max = priority_queue<T, vector<T>, less<T>>;
#define int long long

void solve();

vector<int> P;
const int Mx = 1e4;

signed main() {
    vector<bool> us(Mx);
    for (int i = 2; i < Mx; ++i) {
        if (!us[i]) {
            P.push_back(i);
            for (int j = i * i; j < Mx; j += i) {
                us[j] = true;
            }
        }
    }
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll q = 1;
    cin >> q;
    while (q--) {
        solve();
        cout << "\n";
    }
}

void solve() {
    int n, x;
    cin >> n >> x;
    map<int, int> cnt;
    for (auto w: P) {
        if (w * w > x) {
            break;
        }
        while (x % w == 0) {
            x /= w;
            cnt[w]++;
        }
    }
    if (x > 1) {
        cnt[x]++;
    }
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    map<int, vector<int>> w1;
    for (int i = 0; i < n; ++i) {
        for (auto w: P) {
            if (w * w > a[i]) {
                break;
            }
            int sum = 0;
            while (a[i] % w == 0) {
                a[i] /= w;
                sum++;
            }
            if (sum > 0) {
                w1[w].push_back(sum);
            }
        }
        if (a[i] > 1) {
            w1[a[i]].push_back(1);
        }
    }
    int Ans = 1;
    for (auto [id, e]: w1) {
        int mx = 0;
        for (auto s: e) {
            mx = max(mx, s);
        }
        vector<vector<int>> dp(cnt[id] + 1, vector<int>(mx + 1));
        dp[0][0] = 1;
        for (auto w: e) {
            vector<vector<int>> dp1(cnt[id] + 1, vector<int>(mx + 1));
            for (int i = 0; i <= w; ++i) {
                for (int j = 0; j <= cnt[id]; ++j) {
                    for (int k = 0; k <= mx; ++k) {
                        if (j + min(i, k) <= cnt[id]) {
                            dp1[j + min(i, k)][max(i, k)] += dp[j][k];
                            dp1[j + min(i, k)][max(i, k)] %= MOD;
                        }
                    }
                }
            }
            swap(dp, dp1);
        }
        int s = 0;
        for (int i = 0; i <= mx; ++i) {
            s += dp[cnt[id]][i];
        }
        s %= MOD;
        Ans *= s;
        Ans %= MOD;
        cnt[id] = 0;
    }
    for (auto s: cnt) {
        if (s.second > 0) {
            Ans = 0;
        }
    }
    cout << Ans;
}

На самом деле XOR неотрицательных чисел всегда $$$\leq$$$ их суммы, можете подумать почему.

Используя факт, что XOR множества чисел равен сумме этих чисел, сколько в этом множестве может быть ненулевых чисел?

Для каждой вершины предподсчитайте ближайшего предка, на вертикальном пути до которого нарушается условие хорошего отрезка.

Сведите к задачу к пути длиной не более $$$2 * log(A)$$$, а остальное посчитайте используя предподсчет из подсказки 3.

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
void solve();
 
int main() {
    int t = 1;
    cin >> t;
    while (t --> 0) solve();
    return 0;
}
 
struct Graph {
    vector<int> tin, tout, d;
    vector<vector<pair<int, ll>>> up;
 
    int timer;
 
    void dfs(int v, const vector<vector<int>>& g, const vector<int>& arr, int p = -1) {
        tin[v] = timer++;
        up[0][v] = {p, arr[v]};
        for (int l = 1; l < 20; ++l) {
            if (up[l - 1][v].first == -1) {
                up[l][v] = {-1, 0};
                continue;
            }
            up[l][v].first = up[l - 1][up[l - 1][v].first].first;
            up[l][v].second = up[l - 1][up[l - 1][v].first].second + up[l - 1][v].second;
        }
        for (int u : g[v]) {
            if (u == p) continue;
            d[u] = d[v] + 1;
            dfs(u, g, arr, v);
        }
        tout[v] = timer;
    }
 
    Graph(const vector<vector<int>>& g, const vector<int>& a) : tin(g.size()), tout(g.size()), d(g.size()), up(20, vector<pair<int, ll>>(g.size())) {
        timer = 0;
        dfs(0, g, a);
    }
 
    bool anc(int p, int v) {
        return tin[p] <= tin[v] && tout[p] >= tout[v];
    }
 
    int getLenVertical(int u, int v) {
        if (!anc(u, v)) swap(u, v);
        assert(anc(u, v));
        return d[v] - d[u] - 1;
    }
 
    pair<int, ll> LA(int v, int k) {
        if (k <= 0) return {v, 0};
        ll sum = 0;
        for (int i = 0; i < 20; ++i) {
            if (k >> i & 1) sum += up[i][v].second, v = up[i][v].first;
        }
        return {v, sum};
    }
 
    int LCA(int u, int v) {
        if (anc(u, v)) return u;
        for (int l = 19; l >= 0; --l) {
            if (up[l][u].first == -1 || anc(up[l][u].first, v)) continue;
            u = up[l][u].first;
        }
        return up[0][u].first;
    }
 
    bool lower(int a, int b) {
        return tin[a] < tin[b];
    }
};
 
ll sum(int r) { return r * 1ll * (r + 1) / 2; }
 
ll sumSeg(int l, int r) {
    return sum(r) - sum(l - 1);
}
 
void solve() {
    int n, q; cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    vector<vector<int>> g(n);
    for (int i = 1; i < n; ++i) {
        int u, v; cin >> u >> v;
        --u, --v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    vector<int> parent(n), d(n);
    auto dfs = [&](auto& self, int v, int p = -1) -> void {
        parent[v] = p;
        for (int u : g[v]) {
            if (u == p) continue;
            d[u] = d[v] + 1;
            self(self, u, v);
        }
    };
    dfs(dfs, 0);
 
    vector<int> compressed_parent = parent;
    vector<vector<int>> cG(n);
    for (int v = 0; v < n; ++v) {
        vector<int> path;
        while (compressed_parent[v] > 0 && a[compressed_parent[v]] == 0) {
            path.emplace_back(compressed_parent[v]);
            compressed_parent[v] = compressed_parent[compressed_parent[v]];
        }
        for (auto& x : path) compressed_parent[x] = compressed_parent[v];
        if (a[v] == 0 || !v) continue;
        cG[compressed_parent[v]].emplace_back(v);
    }
 
    vector<int> next_collision(n), sum_collision(n);
    for (int v = 0; v < n; ++v) {
        if (!a[v]) continue;
        next_collision[v] = v;
        int xr = a[v], sm = a[v];
        while (xr == sm && next_collision[v] > -1) {
            next_collision[v] = compressed_parent[next_collision[v]];
            if (next_collision[v] == -1) break;
            xr ^= a[next_collision[v]];
            sm += a[next_collision[v]];
        }
    }
 
    for (int v = 0; v < n; ++v) {
        if (!a[v]) {
            if (!v) next_collision[v] = -1;
            else next_collision[v] = next_collision[compressed_parent[v]];
        }
        sum_collision[v] = d[v];
        if (next_collision[v] > -1) sum_collision[v] -= d[next_collision[v]];
        else sum_collision[v]++;
    }
 
    Graph def(g, sum_collision);
    Graph compressed(cG, sum_collision);
 
    while (q--) {
        int u, v; cin >> u >> v;
        --u, --v;
        if (def.lower(v, u)) swap(u, v);
        int z = def.LCA(u, v);
 
        int cv = (a[v] || !v ? v : compressed_parent[v]), cu = (a[u] || !u ? u : compressed_parent[u]), cz = (a[z] || !z ? z : compressed_parent[z]);
 
        ll ans = 0;
 
        vector<int> L, R, Lspaces = {0}, Rspaces = {0};
 
        if (compressed.d[cv] > compressed.d[cz] + 23) {
            int unt = compressed.LA(cv, compressed.d[cv] - (compressed.d[cz] + 23)).first;
            auto [to, sm] = def.LA(v, d[v] - d[unt]);
            ans += sm, v = to;
        }
 
        if (compressed.d[cu] > compressed.d[cz] + 23) {
            int unt = compressed.LA(cu, compressed.d[cu] - (compressed.d[cz] + 23)).first;
            auto [to, sm] = def.LA(u, d[u] - d[unt]);
            ans += sm, u = to;
        }
 
        while (u != z) {
            int to = compressed_parent[u];
            if (def.anc(to, z)) to = z;
            L.emplace_back(u);
            Lspaces.emplace_back(def.getLenVertical(u, to));
            u = to;
        }
        while (v != z) {
            int to = compressed_parent[v];
            if (def.anc(to, z)) to = z;
            R.emplace_back(v);
            Rspaces.emplace_back(def.getLenVertical(v, to));
            v = to;
        }
        L.emplace_back(z);
        std::reverse(R.begin(), R.end());
        std::reverse(Rspaces.begin(), Rspaces.end());
        for (auto& x : R) L.emplace_back(x);
        for (auto& x : Rspaces) Lspaces.emplace_back(x);
        int j = 0, xr = 0, sum = 0;
        ll cnt = 0;
        for (int i = 0; i < L.size(); ++i) {
            while (j < L.size() && xr == sum) {
                xr ^= a[L[j]], sum += a[L[j]];
                cnt += Lspaces[j] + 1;
                j++;
            }
            if (xr != sum) cnt--;
            ans += sumSeg(cnt - Lspaces[i], cnt);
            if (xr != sum) cnt++;
            xr ^= a[L[i]], sum -= a[L[i]];
            cnt -= Lspaces[i] + 1;
        }
        cout << ans << '\n';
    }
}