Гарні числа#7237

Гарні числа (Розбір)

Ідея

Позначимо числом $A$ добуток множників $a_{1}, a_{2} \dots, a_{N}$ a_1, a_2 \dots, a_N із вхідних даних:

A = a_{1} \cdot a_{2} \cdot \dots \cdot a_{N}

A = a_1 \cdot a_2 \cdot \ldots \cdot a_N

За умовою задачі, нам необхідно знайти в розкладі числа $A$ на прості множники

A = p_{1}^{s_{1}} \cdot p_{2}^{s_{2}} \cdot \dots \cdot p_{L}^{s_{L}}

A = {p_1}^{s_1} \cdot {p_2}^{s_2} \cdot \ldots \cdot {p_L}^{s_L}

таке просте число $p_{l}, 1 \leq l \leq L$ p_l, 1 \le l \le L, для якого $s_{l} \geq 2$ s_l \ge 2.

Воно існуватиме, якщо виконується принаймні одна з умов:

Існують множники $a_{i}, a_{j}, 1 \leq i, j \leq N, i \neq = j$ a_i, a_j, 1 \le i, j \le N, i \ne j такі, що $a_{i} mod p_{l} = 0, a_{j} mod p_{l} = 0$ a_i \bmod p_l = 0, a_j \bmod p_l = 0
Існує множник $a_{i}, 1 \leq i \leq N$ a_i, 1 \le i \le N такий, що $a_{i} mod p_{l}^{2} = 0$ a_i \bmod {p_l}^2 = 0

Розібʼємо початкову на задачу на дві відповідні підзадачі.

Підзадача 1

Знайдемо попарно $НСД (a_{i}, a_{j}), 1 \leq i, j \leq N, i \neq = j$ НСД(a_i, a_j), 1 \le i, j \le N, i \ne j всіх множників числа $A$ . Якщо будь-яка пара множників має спільник дільник більше за одиницю, це і буде відповіддю на задачу.

Складність підзадачі за часом — $O (N^{2})$ O(N^2).

Підзадача 2

Якщо число $a_{i}$ a_i ділиться націло на $p_{l}^{2}$ {p_l}^2, то його можна представити в наступному вигляді:

a_{i} = p_{l}^{2} \cdot x

a_i = {p_l}^2 \cdot x

За допомогою решета Ератосфена знайдемо всі прості дільники $d_{1}, d_{2}, \dots, d_{D}$ d_1, d_2, \ldots, d_D числа $a_{i}$ a_i, які не перевищують $3 1 0^{18} = 1 0^{6}$ \sqrt[3]{10^{18}} = 10^6.

Якщо існує такий дільник $d_{k}, 1 \leq k \leq D$ d_k, 1 \le k \le D, для якого $a_{i} mod d_{k}^{2} = 0$ a_i \bmod {d_k}^2 = 0, то $d_{k}$ d_k — це відповідь на задачу.

Якщо таких дільників серед $d_{1}, d_{2}, \dots, d_{D}$ d_1, d_2, \ldots, d_D немає, тоді поділимо число $a_{i}$ a_i на кожен з них і позначимо результат $a_{i}^{^{'}}$ {a_i}^{'}. Тоді

a_{i}^{^{'}} = p_{l}^{2} \cdot x^{^{'}}

{a_i}^{'} = {p_l}^2 \cdot x^{'}

Оскільки ми знайшли всі дільники до $1 0^{6}$ 10^6, то $p_{l}, x^{^{'}} > 1 0^{6}$ {p_l}, x^{'} \gt 10^6. При цьому, за умовою задачі, $a_{i} \leq 1 0^{18}$ a_i \le 10^{18}, що протирічить попередній умові, оскільки добуток трьох чисел більших за $1 0^{6}$ 10^6 перевищує $1 0^{18}$ 10^{18}. Отже, $x^{^{'}} = 1$ x^{'} = 1.

Залишається перевірити, чи $a_{i}$ a_i є повним квадратом числа $p_{l}$ p_l. Якщо так, то $p_{l}$ p_l — це відповідь на задачу.

Складність підзадачі за часом — $O (3 ∣ a_{i} ∣ \cdot lo g lo g 3 ∣ a_{i} ∣ + N \cdot π (3 ∣ a_{i} ∣))$ O(\sqrt[3]{|a_i|} \cdot \log{\log{\sqrt[3]{|a_i|}}} + N \cdot \pi(\sqrt[3]{|a_i|})),

де $∣ a_{i} ∣$ |a_i| — максимальне значення числа $a_{i}$ a_i, $π (3 ∣ a_{i} ∣)$ \pi(\sqrt[3]{|a_i|}) — кількість простих чисел, які не перевищують $3 ∣ a_{i} ∣$ \sqrt[3]{|a_i|}.

Якщо ми не знайшли відповідь в жодній з підзадач, тоді число $A$ — гарне.

Реалізація

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    const int maxp = 1e6;
    int prime[maxp];
    vector<int> prs;

    for (int i = 2; i < maxp; ++i)
        prime[i] = 1;
    for (int i = 2; i < maxp; ++i)
    {
        if (prime[i])
        {
            prs.push_back(i);
            for (int j = i * 2; j < maxp; j += i)
                prime[j] = 0;
        }
    }

    int n;
    cin >> n;

    unsigned long long a[100];
    for (int i = 0; i < n; ++i)
        cin >> a[i];

    for (int i = 0; i < n; ++i)
        for (int j = i + 1; j < n; ++j)
            if (gcd(a[i], a[j]) > 1)
            {
                cout << gcd(a[i], a[j]) << endl;
                return 0;
            }

    for (int i = 0; i < n; ++i)
    {
        for (int j : prs)
            if (a[i] % j == 0)
            {
                a[i] /= j;
                if (a[i] % j == 0)
                {
                    cout << j << endl;
                    return 0;
                }
            }

        unsigned long long sq = sqrt(a[i]);
        if (sq > 1 && sq * sq == a[i])
        {
            cout << sq << endl;
            return 0;
        }
    }

    cout << "Beautiful" << endl;
}

C++