GCD Loco#12230

GCD Loco (Editorial)

Autor del problema:	Titan493ASST
Preparado por:	Hasan Saleh (MathModel)
Editado por:	Hasan Saleh (MathModel)

Solución

Fije un valor de $k$ . Para cada residuo $j \in {0, \dots, k - 1}$ j\in\{0,\ldots,k-1\}, tome los índices $j, j + k, j + 2 k, \dots < n$ j,\,j+k,\,j+2k,\ldots<n como una clase y deje que $m$ sea su tamaño. Para cualquier primo $p$ , sea $T (p)$ el número total de copias de $p$ (suma de los exponentes de $p$ ) en todos los números de esta clase.

Reclamo A (Invariante dentro de una clase): Si solo mueve un divisor de un elemento de una clase a otro elemento de la misma clase, entonces $T (p)$ no cambia para ningún primo $p$ .

Prueba. Mover un divisor resta su exponente de $p$ de un elemento y lo añade a otro; el total de la clase no cambia (Invariante). $□$

Reclamo B (Mejor gcd para una clase): Para una clase de tamaño $m$ , el mayor gcd que puede forzar dentro de esa clase es igual a

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

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

Prueba. Límite superior: entre $m$ elementos, el mínimo exponente de $p$ no puede exceder el promedio, por lo tanto, como máximo $⌊ T (p) / m ⌋$ \lfloor T(p)/m\rfloor. Podemos lograr esto mediante el Reclamo A, que podemos redistribuir potencias de primos dentro de la clase para que cada elemento obtenga al menos $⌊ T (p) / m ⌋$ \lfloor T(p)/m\rfloor copias de cada $p$ . $□$

Reclamo C (No se necesitan transferencias entre clases). Para un $k$ fijo, existe una secuencia óptima de movimientos que nunca transfiere factores entre diferentes clases.

Prueba (esbozo). Un movimiento entre clases ayuda a una clase mientras perjudica a otra. Si un movimiento elimina factores de una clase actualmente mínima, no puede mejorar el mínimo entre clases; cancele tales movimientos repetidamente para obtener un óptimo solo con movimientos dentro de la clase. $□$

Consecuencia (k fijo y respuesta final). Para un $k$ fijo, el multiconjunto $M$ consiste en los valores de clase del Reclamo B, por lo que

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

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

La respuesta requerida es $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++