Crazy GCD#12230

Crazy GCD (Editorial)

Problem Author:	Titan493ASST
Prepared by:	Hasan Saleh (MathModel)
Edited by:	Hasan Saleh (MathModel)

Solution

Fix a value of $k$ . For each residue $j \in {0, \dots, k - 1}$ j\in\{0,\ldots,k-1\}, take the indices $j, j + k, j + 2 k, \dots < n$ j,\,j+k,\,j+2k,\ldots<n as one class and let $m$ be its size. For any prime $p$ , let $T (p)$ be the total number of copies of $p$ (sum of $p$ -exponents) across all numbers in this class.

Claim A (Invariant inside a class): If you only move a divisor from one element of a class to another element of the same class, then $T (p)$ does not change for any prime $p$ .

Proof. Moving a divisor subtracts its $p$ -exponent from one element and adds it to another; the class total is unchanged (Invariant). $□$

Claim B (Best gcd for one class): For a class of size $m$ , the largest gcd you can force inside that class equals

p \prod p^{⌊ \frac{T ( p )}{m} ⌋} .

\prod_{p} p^{\left\lfloor \dfrac{T(p)}{m}\right\rfloor}.

Proof. Upper bound: among $m$ elements, the minimum $p$ -exponent cannot exceed the average, hence at most $⌊ T (p) / m ⌋$ \lfloor T(p)/m\rfloor. we can achieve this by Claim A that's we can redistribute prime powers within the class so every element gets at least $⌊ T (p) / m ⌋$ \lfloor T(p)/m\rfloor copies of each $p$ . $□$

Claim C (No cross-class transfers needed). For a fixed $k$ , there exists an optimal sequence of moves that never transfers factors between different classes.

Proof (sketch). A cross-class move helps one class while hurting another. If a move removes factors from a currently minimal class, it cannot improve the minimum over classes; cancel such moves repeatedly to get an optimum with only within-class moves. $□$

Consequence (fixed $k$ and final answer). For fixed $k$ , the multiset $M$ consists of the class values from Claim B, so

min (M) = classes min p \prod p^{⌊ \frac{T ( p )}{m} ⌋} .

\min(M)=\min_{\text{classes}}\ \prod_{p} p^{\left\lfloor \dfrac{T(p)}{m}\right\rfloor}.

The required answer is $max_{1 \leq k \leq n} min (M)$ \max_{1\le k\le n}\ \min(M).

//#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4")

#include <bits/stdc++.h>

#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define pb push_back
#define fi first
#define se second

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
template<class T>
using vec = vector<T>;

template<typename T>
bool umin(T &a, T b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}
template<typename T>
bool umax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

#ifdef KoRoVa
#define DEBUG for (bool _FLAG = true; _FLAG; _FLAG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl
template <class ...Ts> auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }
#else
#define DEBUG while (false)
#define LOG(...)
#endif

const int max_n = -1, inf = 1000111222;



void test_case() {
    int n;
    cin >> n;
    vector <vector <pii> > a(n);
    vec<int> cur;
    map <int, int> to;

    auto get_id = [&] (int x) {
        if (to.count(x)) {
            return to[x];
        }
        cur.pb(x);
        return to[x] = len(cur) - 1;
    };

    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        for (int j = 2; j * j <= x; j++) {
            if (x % j == 0) {
                int cnt = 0;
                while (x % j == 0) {
                    x /= j;
                    ++cnt;
                }
                a[i].pb({j, cnt});
            }
        }
        if (x > 1) {
            a[i].pb({x, 1});
        }
        for (auto &j : a[i]) {
            j.first = get_id(j.first);
        }
    }
    int ans = 0;
    vector <int> st(len(cur));
    for (int k = 1; k <= n; k++) {
        int mn = inf;
        for (int j = 0; j < k; j++) {
            int now = 1, cnt = 0;
            for (int x = j; x < n; x += k) {
                ++cnt;
                for (auto &val : a[x]) {
                    st[val.first] += val.second;
                }
            }
            assert(cnt > 0);
            for (int x = j; x < n; x += k) {
                for (auto &val : a[x]) {
                    int gg = st[val.first] / cnt;
                    if (gg) {
                        while (gg) {
                            --gg;
                            now *= cur[val.first];
                        }
                    }
                    st[val.first] = 0;
                }
            }
            umin(mn, now);
        }
        umax(ans, mn);
    }
    cout << ans << '\n';
}



int main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);

    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int t = 1;

     cin >> t;

    while (t--) test_case();

    return 0;
}

/*
KoRoVa!
*/

C++