Editorial for Trực nhật

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

`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;
}

Comments

There are no comments at the moment.