GCD Fou#12230

GCD Fou (Corrigé)

Auteur du problème:	Titan493ASST
Préparé par:	Hasan Saleh (MathModel)
Édité par:	Hasan Saleh (MathModel)

Solution

Fixez une valeur de $k$ . Pour chaque résidu $j \in {0, \dots, k - 1}$ j\in\{0,\ldots,k-1\}, prenez les indices $j, j + k, j + 2 k, \dots < n$ j,\,j+k,\,j+2k,\ldots<n comme une classe et laissez $m$ être sa taille. Pour tout nombre premier $p$ , notons $T (p)$ le nombre total de copies de $p$ (somme des $p$ -exposants) à travers tous les nombres dans cette classe.

Affirmation A (Invariant à l'intérieur d'une classe): Si vous déplacez un diviseur d'un élément d'une classe à un autre élément de la même classe, alors $T (p)$ ne change pas pour tout nombre premier $p$ .

Preuve. Déplacer un diviseur soustrait son $p$ -exposant d'un élément et l'ajoute à un autre ; le total de la classe reste inchangé (Invariant). $□$

Affirmation B (Meilleur pgcd pour une classe): Pour une classe de taille $m$ , le plus grand pgcd que vous pouvez forcer à l'intérieur de cette classe est égal à

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

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

Preuve. Limite supérieure : parmi $m$ éléments, le minimum $p$ -exposant ne peut pas dépasser la moyenne, donc au maximum $⌊ T (p) / m ⌋$ \lfloor T(p)/m\rfloor. Nous pouvons y parvenir par l'Affirmation A, car nous pouvons redistribuer les puissances des premiers au sein de la classe afin que chaque élément obtienne au moins $⌊ T (p) / m ⌋$ \lfloor T(p)/m\rfloor copies de chaque $p$ . $□$

Affirmation C (Pas de transferts inter-classes nécessaires). Pour un $k$ fixe, il existe une séquence optimale de mouvements qui ne transfère jamais de facteurs entre différentes classes.

Preuve (esquisse). Un mouvement inter-classe aide une classe tout en nuisant à une autre. Si un mouvement retire des facteurs d'une classe actuellement minimale, il ne peut pas améliorer le minimum entre les classes ; annulez de tels mouvements de manière répétée pour obtenir un optimum uniquement avec des mouvements intra-classe. $□$

Conséquence (k fixe et réponse finale). Pour un $k$ fixe, l'ensemble multiset $M$ consiste en les valeurs de classe de l'Affirmation B, donc

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}.

La réponse requise est $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++