Solutions of Division problem

Select solution language

Nhận xét đầu tiên: để

$\lfloor\frac{a}{b}\rfloor\lfloor\frac{a}{c}⌋\lfloor\frac{b}{c}\rfloor \gt 0$ thì bộ ba số này phải thỏa điều kiện

$a \gt b \gt c$ .

$(1)$ Chỉ riêng với nhận xét này, bạn đã có thể giảm thời gian chạy code trâu xuống

$6$ lần. Gọi

$f(x)$ là tổng

$⌊\frac{x}{y}⌋$ với mọi

$y$ ∈

$A$ và

$1 \le y \le x$ . - Ta nhận thấy

$x$ và

$f(x)$ tỷ lệ thuận với nhau. - Ngoài ra, khi xét đến

$x$ , ta thấy rằng chỉ có các giá trị

$y$ là ước của

$x$ mới làm tăng

$f(x)$ lên

$1$ .

$(2)$ Từ đây, ta có một ý tưởng là cố định

$a$ và

$b$ trước, khi này ta sẽ ngay lập tức có được

$\lfloor\frac{a}{b}\rfloor$ , việc còn lại là tính tổng của các

$\lfloor\frac{a}{c}\rfloor\lfloor\frac{b}{c}\rfloor$ thôi. Khi đã cố định

$a$ , ta duyệt qua các giá trị

$b$ sao cho

$b \lt a$ đồng thời

$b$ ∈

$[1 ... a)$ . Như đã nói ở trên, ý tưởng chính của thuật toán là khi duyệt đến

$b$ , ta phải tính được tổng

$\lfloor\frac{a}{c}\rfloor\lfloor\frac{b}{c}\rfloor$ . Để làm được việc này, ta có thể dựa vào nhận xét

$(2)$ : chỉ cần duyệt qua các giá trị

$c$ là ước của

$b$ , bước này tốn

$O($ số ước của

$b)$ . Để liệt kê được các ước của

$b$ , ta có thể dựa vào sàng nguyên tố để có được sàng ước và chuẩn bị trước với độ phức tạp

$O(n * log n)$ Độ phức tạp thời gian: ~

$O(n^2 * t + n * logn)$

$(t$ là hằng số biểu diễn cho bước duyệt qua các

$c$ làm

$f(b)$ thay đổi,

$t$ ~

$8$ ) *Note: mình thấy trong phần all submissions cũng có nhiều người dùng prefix sum, nhưng vì quá gà nên mình không hiểu được ToT.