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

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)\) và \(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

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)\) và \((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

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

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

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