\(\color{red}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.0}}}}}\)

\(\color{red}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}\)

\(\color{red}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}\)

\(\color{orange}{\text{Hint 1 <Brute-force>}}\)

• Thử từng số nguyên \(v\) trong đoạn \([2..x]\) và tìm \(f\) thỏa \(v ^ f = x\)

• Kết quả là số \(f\) lớn nhất tìm được

\(\color{orange}{\text{Hint 2 <Branch-and-bound> <Binary-search>}}\)

• Thay vì thử các số nguyên bất kì, ta có thể chỉ cần thử các ước của \(x\)

• Ta cũng có thể tìm số mũ \(f\) bằng chặt nhị phân để nhanh hơn

\(\color{orange}{\text{Hint 3 <Factorization>}}\)

• Giả sử tồn tại cặp \((v, f)\) thỏa \(v ^ f = x\)

\(v\) càng nhỏ thì \(f\) càng lớn

Có \(v\) là ước của \(x\), vậy để tối thiểu hóa \(v\) thì \(v\) sẽ bao gồm các ước nguyên tố của \(x\)

• Chúng ta sẽ phân tích thừa số nguyên tố của \(x\)

Với mỗi số nguyên tố, ta đếm số lần xuất hiện (tần số xuất hiện số nguyên tố)

Kết quả cần tìm là bội chung nhỏ nhất của các tần số

\(\color{orange}{\text{Hint 4 <Branch-and-bound> <Factorization> <Math>}}\)

• Chúng ta có thể phân tích thừa số nguyên tố từng số \(a, b, c\) vì \(a \times b \times c = x\)

• Mỗi khi phân tích một số \(n\) thành thừa số nguyên tố, ta chỉ cần tìm các ước của nó và chia xuống tới khi \(n = 1\)

• Giả sử có \(a \times b = n\) và \(1 \leq a \leq b \leq n\)

Ta có \(a \times b \leq \sqrt{n} \times \sqrt{n} \Rightarrow 1 \leq a \leq b \leq \sqrt{n} \leq n\)

Vậy nếu \(a\) là ước của \(n\) thì ước còn lại \(\leq \sqrt{n}\)

• Vậy ta chỉ cần duyệt đến \(\sqrt{n}\) để tìm ước nguyên tố \(\leq \sqrt{n}\) của \(n\) khi \(n\) là hợp số

• Thế trong trường hợp \(n\) nguyên tố ta làm thế nào ?

Ta duyệt loại bỏ các ước nguyên tố \(\leq \sqrt{x}\), phần còn lại hoặc là \(n\) nguyên tố hoặc \(n = 1\)

Vậy nếu sau quá trình trên \(n > 1\) thì \(n\) là số nguyên tố

\(\color{green}{\text{Preference AC Code }}\): Branch-and-bound, Factorization

\(^{^{\color{purple}{\text{Complexity : }} O(\sqrt{max\_val})\ \color{purple}{\text{time}}\ ||\ O(\sigma_0(a \times b \times c))\ \color{purple}{\text{memory}}}}\)

map<ll, int> M;
void fact(ll x)
{

    int sqrtx = sqrt(x);
    for (int d = 2; d <= sqrtx && d <= x; ++d)
    {
        while (x % d == 0)
        {
            M[d]++;
            x /= d;
        }
    }
    if (x > 1) M[x]++, x = 1;
}

int main()
{
    fact(readLong());
    fact(readLong());
    fact(readLong());

    vector<int> fre;
    for (pair<int, int> e : M)
        fre.push_back(e.second);

    int res = fre.front();
    for (int i = 1; i < fre.size(); ++i)
        res = gcd(res, fre[i]);

    cout << res;
    return 0;
}

\(\color{green}{\text{Preference AC Code }}\): Branch-and-bound, Factorization, Bitwise

\(^{^{\color{purple}{\text{Complexity : }} O(\sqrt{max\_val})\ \color{purple}{\text{time}}\ ||\ O(\sigma_0(a \times b \times c))\ \color{purple}{\text{memory}}}}\)

map<ll, int> M;
void fact(ll x)
{
    int k = __builtin_ctzll(x);
    M[2] += k;
    x >>= k;

    int sqrtx = sqrt(x);
    for (int d = 3; d <= sqrtx && d <= x; d += 2)
    {
        while (x % d == 0)
        {
            M[d]++;
            x /= d;
        }
    }
    if (x > 1) M[x]++;
}

int main()
{
    fact(readLong());
    fact(readLong());
    fact(readLong());

    vector<int> fre;
    for (pair<int, int> e : M)
        fre.push_back(e.second);

    int res = fre.front();
    for (int i = 1; i < fre.size(); ++i)
        res = gcd(res, fre[i]);

    cout << res;
    return 0;
}