Số lượng ước số

Xem PDF

Điểm: 200 (p) Thời gian: 2.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Ký hiệu \(D(n)\) là số lượng ước số của số tự nhiên \(n\), ví dụ: \(D(10)=4\)\(D(12)=6\). Với \(L\)\(R\) cho trước \((L\leq R)\), hãy tính tổng \(D(L)+D(L+1)+...+D(R-1)+D(R)\).

Input

  • Dòng đầu chứa số nguyên dương \(T\leq 10^6\) là số lượng câu hỏi.

  • \(T\) dòng sau, mỗi dòng chứa hai số nguyên dương \(L\)\(R\) thể hiện một câu hỏi \(\left(1\leq L\leq R\leq 10^6\right)\).

Output

  • Gồm \(T\) dòng, mỗi dòng chứa một số nguyên dương là câu trả lời cho câu hỏi tương ứng.

Example

Test 1

Input
2
1 12
4 5
Output
35
5

Bình luận


  • 0
    Sang_Nguyen_Dang 11:29 a.m. 24 Tháng 1, 2024

    Đã rất cố gắng nhưng không tài nào ac py3 đc 🙂


    • 0
      new4letuantu 3:47 p.m. 16 Tháng 7, 2022

      Tại sao chạy test 1 ở ngoài đúng mà vô trong này lại tle nhỉ :))

      1 phản hồi

      • 0
        N7hoatt 5:51 p.m. 1 Tháng 8, 2020

        quên thay endl bằng "\n" nên mất 5 đấm vì ngu


        • 0
          Lê_Gia_Khánh 9:55 p.m. 7 Tháng 7, 2020

          Dùng thư viện bits/stdc++.h thì tle mà dùng thư viện iostream lại ac :))

          1 phản hồi

          • 5
            SPyofgame 8:09 a.m. 20 Tháng 6, 2020 chỉnh sửa 2

            Spoiler Alert


            Hint 1

            • Với mỗi truy vấn: Duyệt trâu tính \(\Sigma_{x = l}^{r}(\ D(x) \ )\)

            Ta cần tính \(res = \Sigma_{x = l}^{r}(\ \ \Sigma_{d\ |\ x}^{d \in N}(1) \ \ )\)

            Có nghĩa là ta tính tổng các giá trị \(D(x)\) với mọi \(x \in [l, r]\)


            Reference TLE code | \(O(q \times max\_r \times max\_r)\) time | \(O(1)\) auxiliary space | Brute-forces

            C++
            int query()
            {
                int l, r;
                cin >> l >> r;
            
                ll res = 0;
                for (int x = l; x <= r; ++x)
                    for (int d = 1; d <= x; ++d) 
                        sum += (x % d == 0);
            
                return res;
            }
            

            Hint 2

            • Tiền xử lí trước \(D(x) = Sigma_{d\ |\ x}^{d \in N}(d)\) với mọi \(x \in [1, max\_r]\)

            Giờ ta chỉ cần duyệt qua \(x \in [l, r]\) và tăng \(res += D(x)\)\(D(x)\) đã được tính nên mất \(O(1)\)


            Reference AC code | \(O(max\_r \times max\_r)\) time + \(O(q) \times O(max\_r)\) query | \(O(n)\) auxiliary space | Brute-forces, Precalculation

            C++
            vector<int> divcnt; /// divisors_count
            void precalculation(int lim = 1e6 + 500) {
                divcnt.assign(lim + 1, 0);
                for (int x = 1; x <= lim; ++x)
                    for (int d = 1; d <= x; ++d) 
                        divcnt[x] += (x % d == 0);
            }
            
            int query()
            {
                int l, r;
                cin >> l >> r;
            
                ll res = 0;
                for (int x = l; x <= r; ++x)
                    res += divcnt[x];
            
                return res;
            }
            

            Hint 3

            • Khi \((a | n)\) ta có \(n = a * b\) với \((a \leq b)\)\((a, b \in Z)\)

            Dễ chứng minh được \(1 \leq a \leq \sqrt n \leq b \leq n\)

            Với mỗi ước \(d\) của \(x\) ta cũng có \(\frac{x}{d}\) cũng là ước của \(x\)

            Từ đó ta chỉ cần duyệt đến \(\sqrt n\) và tăng biến đếm 2 lần khi \((a \neq b)\)

            Reference AC code | \(O(max\_r \times \sqrt{max\_r})\) time + \(O(q) \times O(max\_r)\) query | \(O(n)\) auxiliary space | Brute-forces, Precalculation

            C++
            vector<int> divcnt; /// divisors_count
            void precalculation(int lim = 1e6 + 500) {
                divcnt.assign(lim + 1, 0);
                for (int x = 1; x <= lim; ++x)
                {
                    int sqrtx = sqrt(x);
                    for (int d = 1; d <= sqrtx; ++d) 
                        if (x % d == 0)
                            divcnt[x] += 1 + (d != x / d);
                }
            }
            

            Hint 4

            • Ta cũng có thể tiền xử lí kết quả của từng đoạn \([l, r]\)

            Tuy nhiên việc này sẽ tốn thời gian lâu (2 vòng lặp \(max\_r\) cho từng cặp \([l, r] \in [1, max\_r]\))

            Nhận xét rằng: \(D(l) + ... + D(r) = (D(1) + ... + D(r)) - (D(1) + ... + D(l - 1))\)

            Gọi \(f(n) = D(1) + ... + D(n)\) hay \(f(n) = D(n) + f(n - 1)\)

            Ta có thể tiền xử lí giá trị các đoạn \([l, r] = f(r) - f(l - 1)\) trong \(O(max\_r)\)

            Reference AC code | \(O(max\_r \times \sqrt{max\_r})\) time + \(O(q) \times O(1)\) query | \(O(n)\) auxiliary space | Brute-forces, Precalculation, Partial-sum

            C++
            vector<int> divcnt; /// divisors_count
            vector<ll>  pfs;    /// prefixsum
            void precalculation(int lim = 1e6 + 500) {
                divcnt.assign(lim + 1, 0);    
                   pfs.assign(lim + 1, 0);
            
                for (int x = 1; x <= lim; ++x)
                {
                    int sqrtx = sqrt(x);
                    for (int d = 1; d <= sqrtx; ++d) 
                        if (x % d == 0)
                            divcnt[x] += 1 + (d != x / d);
            
                    pfs[x] = divcnt[x] + pfs[x - 1];
                }
            }
            
            int query()
            {
                int l, r;
                cin >> l >> r;
                return pfs[r] - pfs[l - 1];
            }
            

            Hint 5

            • Đảo nhãn: Tìm ước ta cần kiểm tra tính chia hết nhưng tìm bội thì không !

            Thay vì tìm mọi ước \(d\) của \(x\) ta sẽ tăng giá trị các bội \(x\) của \(d\) lên 1


            Reference AC code | \(O(max\_r \times \log_2(max\_r))\) time + \(O(q) \times O(1)\) query | \(O(n)\) auxiliary space | Brute-forces, Precalculation, Partial-sum

            C++
            vector<int> divcnt; /// divisors_count
            vector<ll>  pfs;    /// prefixsum
            void precalculation(int lim = 1e6 + 500) {
                divcnt.assign(lim + 1, 0);
                   pfs.assign(lim + 1, 0);
            
                for (int d = 1; d <= lim; ++d) {
                    for (int x = d; x <= lim; x += d)
                        divcnt[x]++;
            
                    pfs[d] = divcnt[d] + pfs[d - 1];
                }
            }
            
            int query()
            {
                int l = readInt();
                int r = readInt();
                return pfs[r] - pfs[l - 1];
            }