Crazy GCD#12230

Crazy GCD (Həll təhlili)

Problem Müəllifi:	Titan493ASST
Hazırlayan:	Hasan Saleh (MathModel)
Redaktə edən:	Hasan Saleh (MathModel)

Həll

Bir $k$ dəyərini müəyyən edin. Hər bir qalıq $j \in {0, \dots, k - 1}$ j\in\{0,\ldots,k-1\} üçün, indeksləri $j, j + k, j + 2 k, \dots < n$ j,\,j+k,\,j+2k,\ldots<n bir sinif kimi götürün və $m$ onun ölçüsü olsun. Hər hansı bir asal $p$ üçün, $T (p)$ bu sinifdəki bütün ədədlər arasında $p$ -nin ümumi nüsxələrinin sayını (p-nin eksponentlərinin cəmi) ifadə edir.

İddia A (Sinif daxilində invariant): Əgər siz yalnız bir sinifin bir elementindən digər elementinə bir böləni köçürsəniz, onda $T (p)$ hər hansı bir asal $p$ üçün dəyişmir.

Sübut. Bir böləni köçürmək onun $p$ -eksponentini bir elementdən çıxarır və digərinə əlavə edir; sinifin cəmi dəyişmir (Invariant). $□$

İddia B (Bir sinif üçün ən yaxşı gcd): Bir ölçüsü $m$ olan sinif üçün, o sinifdə məcbur edə biləcəyiniz ən böyük gcd

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

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

Sübut. Yuxarı sərhəd: $m$ element arasında, minimum $p$ -eksponent ortalamadan yuxarı ola bilməz, buna görə də ən çox $⌊ T (p) / m ⌋$ \lfloor T(p)/m\rfloor. Bunu İddia A ilə əldə edə bilərik ki, sinif daxilində asal gücləri yenidən paylaya bilərik ki, hər bir element hər $p$ üçün ən azı $⌊ T (p) / m ⌋$ \lfloor T(p)/m\rfloor nüsxə alsın. $□$

İddia C (Siniflər arasında köçürmələrə ehtiyac yoxdur). Müəyyən $k$ üçün, fərqli siniflər arasında faktorları köçürmədən optimal hərəkətlərin bir ardıcıllığı mövcuddur.

Sübut (qısa). Siniflər arasında bir köçürmə bir sinifi kömək edərkən, digərini zədələyir. Əgər bir köçürmə hazırda minimal olan bir sinifdən faktorları çıxarırsa, bu, siniflər arasında minimumu yaxşılaşdıra bilməz; belə köçürmələri dəfələrlə ləğv edin ki, yalnız sinif daxilindəki köçürmələrlə optimum əldə edəsiniz. $□$

Nəticə (müəyyən $k$ və son cavab). Müəyyən $k$ üçün, çoxluq $M$ İddia B-dən sinif dəyərlərindən ibarətdir, belə ki

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

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

Tələb olunan cavab $max_{1 \leq k \leq n} min (M)$ \max_{1\le k\le n}\ \min(M)-dir.

//#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++