Hướng dẫn giải của Bedao Regular Contest 21 - Số chín ước

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban. 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

void Process() {
    ll n; cin >> n;

    for(ll u = 2; u * u * u * u <= n; ++u) {
        if(n % u != 0) continue;
        ll a = n / u;
        if(a % u != 0) break;
        a /= u;
        ll mid = sqrt(a);
        bool is_prime = 1;
        for(ll x = 2; x * x <= mid; ++x) if(mid % x == 0) is_prime = 0;
        if(mid != u && mid * mid == a && is_prime) return void(cout << "YES\n");
        break;
    }
    ll x = 2;
    while(x * x * x * x * x * x * x * x < n) ++x;
    bool is_prime = 1;
    for(ll i = 2; i * i <= x; ++i) if(x % i == 0) is_prime = 0;
    cout << (is_prime && x * x * x * x * x * x * x * x == n ? "YES\n" : "NO\n");
}

int main() {
    cin.tie(NULL)->sync_with_stdio(false);
    int t; cin >> t;
    while(t--) Process();
    return 0;
}

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • 13
    KAKOII  đã bình luận lúc 4, Tháng 3, 2025, 8:09 ← chỉnh sửa

    Lời giải:

    Khi phân tích một số ~x~ thành các thừa số nguyên tố: ~x = p_1^{q_1} \times p_2^{q_2} \times \dots \times p_n^{q_n}~, ta có thể tính được số lượng ước của ~x~ bằng công thức:

    $$(q_1 + 1) \times (q_2 + 1) \times \dots \times (q_n + 1)$$

    Từ công thức trên, ta có thể xác định các số có ~9~ ước bằng cách tìm các số có dạng:

    ~a^2 \times b^2~ hoặc ~c^8~ với ~a, b, c~ là các số nguyên tố.