Trực nhật

Xem PDF
Thời gian:
Pypy 3 5.0s
Python 3 15.0s
Bộ nhớ:
Pypy 3 512M
Python 3 512M
Tác giả:
CaiWinDao
Dạng bài
Điểm: 300 (p) Thời gian: 1.1s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Lớp \(11\) chuyên Tin có \(n\) học sinh, thầy chủ nhiệm Linh Phan muốn chọn ra một số bạn ở lại trực nhật lớp. Để thêm tính hấp dẫn và công bằng, thầy viết một đoạn code cấp cho mỗi bạn một số tự nhiên ngẫu nhiên và quy định rằng, nếu bạn nào nhận được số có tổng các ước dương của nó nhỏ hơn hai lần số đó thì phải đi trực nhật.

Một lần không may mắn, máy tính của thầy Linh Phan đã sinh ra các số mà sau khi cấp phát cho học sinh thì không có học sinh nào phải ở lại trực nhật. Rút kinh nghiệm từ lần đó, thầy đã chuẩn bị sẵn một dãy số, rồi nhờ các em đội tuyển Tin tính xem có bao nhiêu số có tổng các ước dương nhỏ hơn hai lần số đó, nếu số lượng số này đủ nhiều thì thầy sẽ lấy dãy số đó để cấp cho các bạn trong lớp.

Yêu cầu: Cho số nguyên dương \(n\) và dãy số \(a_1\), \(a_2\),..., \(a_{n – 1}\), \(a_n\). Hãy giúp thầy Linh Phan xác định xem với dãy số này thì có bao nhiêu em học sinh phải làm nhiệm vụ trực nhật.

Input

  • Dòng đầu ghi số nguyên dương \(n\), số học sinh trong lớp.
  • Dòng thứ hai gồm \(n\) số nguyên dương \(a_1\), \(a_2\),..., \(a_{n–1}\), \(a_n\).

Output

  • Gồm một số duy nhất là số học sinh phải ở lại trực nhật tương ứng với dãy số input.

Constraints

  • \(N\leq 10^6\)
  • \(a_i\leq 5.10^6\)

Scoring

  • Subtask \(1\) (\(70\%\) số điểm): \(N\leq 10^3, a_i\leq 10^4\)
  • Subtask \(2\) (\(15\%\) số điểm): \(N\leq 10^4, a_i\leq 5.10^6\)
  • Subtask \(3\) (\(15\%\) số điểm): Không có ràng buộc gì thêm

Example

Test 1

Input 
5
3 6 9 12 9
Output 
3
Note
  • Tổng ước dương của các số là:
  • Số \(3\): \(1+3=4<2.3=6\);
  • Số \(6\): \(1+2+3+6=2.6=12\)
  • Số \(9\): \(1+3+9=13<2.9=18\)
  • Số \(12\): \(1+2+3+4+6+12=28>2.12=24\)

  • Số \(9\): \(1+3+9=13<2 * 9=18\)

  • Vậy có \(3\) số có tổng ước nhỏ hơn hai lần nó là: \(3, 9 ,9\).

Bình luận


  • 1
    VoBaThongL921    4:56 p.m. 13 Tháng 10, 2021

    dùng hàm để sàng số ước thì tle còn gắn vô hàm main luôn thì ac:)

    1 phản hồi

    • -3
      minhtuanitk20    1:32 p.m. 2 Tháng 10, 2021

      thầy của em


      • -2
        THOANGLQDT    11:00 a.m. 16 Tháng 1, 2021

        1234456789


        • 0
          Truongkhaiminh    8:16 p.m. 13 Tháng 11, 2020

          https://ideone.com/snv9Mz


          • 0
            SPyofgame    7:47 p.m. 14 Tháng 6, 2020 ← chỉnh sửa 2

            Hổng biết còn thuật nào hay hơn hông ta OwO

            • Current Best Code | 917ms | 27.97ms | C++ 11

            Time Complexity: \(O(n\) \(log_2 n)\)

            Space Complexity: O(n)$


            • -18
              hieucosintancosi    5:15 p.m. 14 Tháng 6, 2020 ← đã chỉnh sửa

              Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.


              • 2
                SPyofgame    5:12 p.m. 14 Tháng 6, 2020 ← chỉnh sửa 13

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