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.
NHQ0914
Created at
6 likes