Божевільний НСД#12230
Увійти

Автор проблеми:

Titan493ASST

Підготовлено:

Хасан Салех (MathModel)

Редаговано:

Хасан Салех (MathModel)

Рішення

Зафіксуйте значення . Для кожного залишку j\in\{0,\ldots,k-1\} візьміть індекси j,\,j+k,\,j+2k,\ldots<n як один клас і нехай буде його розміром. Для будь-якого простого числа , нехай буде загальною кількістю копій (сума -експонент) серед усіх чисел у цьому класі.

Твердження A (Інваріант всередині класу): Якщо ви лише перемістите дільник з одного елемента класу в інший елемент того ж класу, то не змінюється для будь-якого простого числа .

Доказ. Переміщення дільника віднімає його -експонент від одного елемента і додає до іншого; загальна сума класу залишається незмінною (інваріант).

Твердження B (Найкращий НСД для одного класу): Для класу розміром , найбільший НСД, який ви можете примусити всередині цього класу, дорівнює

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

Доказ. Верхня межа: серед елементів мінімальний -експонент не може перевищувати середнє, отже, не більше ніж \lfloor T(p)/m\rfloor. Ми можемо досягти цього за допомогою Твердження A, що ми можемо перерозподілити прості степені в межах класу, так що кожен елемент отримує принаймні \lfloor T(p)/m\rfloor копій кожного .

Твердження C (Необхідність перехресних передач не потрібна). Для фіксованого існує оптимальна послідовність переміщень, яка ніколи не передає фактори між різними класами.

Доказ (нарис). Перехресний рух допомагає одному класу, завдаючи шкоди іншому. Якщо рух видаляє фактори з нині мінімального класу, він не може покращити мінімум між класами; скасуйте такі рухи повторно, щоб отримати оптимум лише з рухами всередині класу.

Наслідок (фіксований і остаточна відповідь). Для фіксованого , мультибезліч складається з класових значень з Твердження B, тому

\min(M)=\min_{\text{класів}}\ \prod_{p} p^{\left\lfloor \dfrac{T(p)}{m}\right\rfloor}.

Вимога відповіді - це \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++