Hướng dẫn cho Trực nhật

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: SPyofgame

`Spoiler Alert`

Hint 1

Gọi $check(x)$ là hàm kiểm tra xem $x$ có thỏa mãn hay không

Duyệt qua từng số, tăng biến đếm nếu $check(x) = true$

$Result$ = số lượng $x \in A$ thỏa $check(x) = true$

Hint 2

$check(x) = true$ <=> $divisors\_sum(x) < 2 * x$

Ta cần tính $divisor\_sum(x)$ thì việc còn lại là kiểm tra $O(1)$ khi duyệt $O(n)$

Hint 3

Mathematics Approach:

Có $x = p_1 ^ {f_1} * p_2 ^ {f_2} * ... * p_k ^ {f_k}$ với $p_i$ là thừa số nguyên tố và $f_i$ là số mũ nguyên dương

Có $divisors\_sum(x) = \Sigma(unique$ $t = p_1 ^ {f_1^{''} \leq f_1} * p_2 ^ {f_2^{''} \leq f_2} * ... * p_k ^ {f_k^{''} \leq f_k})$

<=> $divisors\_sum(x) = \frac{p_1 ^ {f_1 + 1} - 1}{p_1 - 1} * \frac{p_2 ^ {f_2 + 1} - 1}{p_2 - 1} * ... * \frac{p_k ^ {f_k + 1} - 1}{p_k - 1}$

Precalculation Approach:

Gọi $1 \leq d \leq x \leq max$

Để tiền xử lí thì $\forall x$ ta tìm các ước $d$ và tính tổng

<=> Lần lượt tăng giá trị các bội $x$ lên $d$ đơn vị

Hint 4

Mathematics Approach:

Sàng nguyên tố để lấy tất cả các số nguyên tố $p \leq max$

Khởi tạo $sum = $ rồi liên tục phân tích nhân tử để tách ra từng phần $p_i ^ {f_i}$ để thực hiện tính toán

Precalculation Approach:

Khởi tạo $divisors\_sum(x) = 0$ $\forall x \in [1..max]$

$\forall x \in [1..max]$ tăng giá trị $divisors\_sum[k * x]$ lên thêm $x$ đơn vị ($k \in ℕ^*$ and $k * x \leq max$)

Reference AC code |$O(n)$ time + $O(n)$ * $O(log_2 n)$ query | $O(n)$ auxiliary space | Online Solving, Sieve, Math

C++

vector<int> prime; /// mang cac so nguyen to
vector<int> lpf;   /// lowest prime factor | lpf[x] la uoc nguyen to nho nhat cua x

/// Sang nguyen to trong O(n)
void sieve(int lim = LIM) {
    prime.assign(1, 2);
    lpf.assign(lim + 1, 2);

    lpf[1] = 1; /// can than lap vo han
    for (int i = 3; i <= lim; i += 2) {
        if (lpf[i] == 2) prime.pb(lpf[i] = i);
        for (int j = 0; j < sz(prime) && prime[j] <= lpf[i] && prime[j] * i <= lim; ++j)
            lpf[prime[j] * i] = prime[j];
    }
}

/// Tinh (x ^ n) trong O(log n)
inline ll pw(ll x, ll n) {
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * x;
        n >>= 1;
        x = x * x;
    }
    return res;
}

/// Kiem tra xem (x) co thoa man khong
bool check(int x) {
    int t = x;

    ll sum = 1;
    while (x > 1) {
        /// p la so nguyen to, f la so mu
        int p = lpf[x], f = 0;

        /// chia x cho uoc nguyen to nho nhat cua x toi khi nao khong con uoc do nua
        /// <=> tach nhan tu (p ^ f) ra khoi x
        do x /= p, f++; while (p == lpf[x]);

        /// dung cong thuc toan hoc
        sum *= (pw(p, f + 1) - 1) / (p - 1); 
    }

    return sum < 2 * t;
}

/// Ham chinh
int main()
{
    /// Tien xu li
    sieve(5e6 + 100);

    /// Xu li
    int res = 0;
    for (int n = readInt(); n--; res += check[readInt()]); /// Duyet qua tung phan tu

    /// Xuat ket qua
    cout << res;
    return 0;
}

Reference AC code | $O(n$ $log_2 n)$ time + $O(n)$ * $O(1)$ query | $O(n)$ auxiliary space | Online Solving, Precalculation

C++

int main()
{
    /// Tien xu li: div_sum[x] = tong cac uoc duong cua x
    int lim = 5e6;
    vector<int> div_sum(lim + 1, 0);
    for (int i = 1; i <= lim; ++i)
        for (int j = i; j <= lim; j += i) /// Duyet qua cac boi cua (i)
            div_sum[j] += i;              /// Lan luot cong vao boi (i) cac uoc cua no

    /// Tien xu li: div_sum[x] < 2 * x <=> check[x] = true
    vector<bool> check(lim + 1);
    for (int i = 0; i <= lim; ++i)
        check[i] = (div_sum[i] < i * 2);

    /// Xu li
    int res = 0;
    for (int n = readInt(); n--; res += check[readInt()]); /// Duyet qua tung phan tu

    /// Xuat ket qua
    cout << res;
    return 0;
}

Bình luận

Không có bình luận nào.