Editorial for Bedao Mini Contest 08 - PAIRS


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: bedao

Subtask 1:

Duyệt toàn bộ cặp ~1 \le i < j \le n~ và kiểm tra 2 điều kiện: ~i \times j \le m~ và ~i \times j~ là số chính phương.

Độ phức tạp: ~\mathcal{O}(n^2)~

Subtask 2:

Nhận thấy ~i \le \sqrt{m}~. Với mỗi ~i~, ta duyệt ~j~ từ ~i+1~ đến ~\min(n,m/i)~. Với mỗi cặp ~(i,j)~ ta chỉ cần kiểm tra điều kiện ~i \times j~ có phải số chính phương hay không.

Độ phức tạp: ~\mathcal{O}(m\log m)~

Subtask 3:

Với mỗi số ~i~, ta gọi ~p[i] = i / x~ với ~x~ là số chính phương lớn nhất mà ~i~ chia hết. Ta có thể tính được ~p[i]~ bằng cách phân tích thừa số nguyên tố của số ~i~ ra và đặt ~p[i] = ~ tích các ước nguyên tố có lũy thừa lẻ. Khi đó chi phí chuẩn bị mảng ~p~ là ~\mathcal{O}(n\log n)~

Nhận xét: tích hai số ~i~ và ~j~ là số chính phương khi và chỉ khi ~p[i] = p[j]~. Với mỗi ~j~, ta sẽ đếm số lượng ~i < j~ mà ~p[i]=p[j]~ và ~i \times j \le m~. Ta có thể làm việc này bằng hai con trỏ, chi phí là ~\mathcal{O}(n)~.

Độ phức tạp: ~\mathcal{O}(n \log n)~

Subtask 4:

Ta sẽ dựng mảng ~p~ nhanh hơn như sau:

for (int i = 1; i <= n; i++) 
    p[i] = i;
for (int i = 2; i*i <= n; i++) {
    for (int j = i*i; j <= n; j += i*i)
        p[j] = j / (i*i);
}

Với cách này chi phí xây dựng mảng ~p~ sẽ là ~\mathcal{O}(n)~.

Độ phức tạp: ~\mathcal{O}(n)~


Comments

Please read the guidelines before commenting.


There are no comments at the moment.