Editorial for Bedao Mini Contest 14 - EXAMINE


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

~\large lcm(x, y) = gcd(x, y)^2~

~\iff~ ~\Large\frac{x \cdot y}{\mathcal{gcd(x, y)}} = gcd(x, y)^2~

~\iff~ ~\Large\frac{x}{gcd(x, y)} \cdot \frac{y}{gcd(x, y)} = n~

Vì ~\large gcd(\frac{x}{gcd(x, y)} \cdot \frac{y}{gcd(x, y)}) = 1~ nên ta cần tính tìm các cặp ~(a, b)~ sao cho ~a \cdot b = n~ và ~gcd(a, b) = 1~ sau đó nhân với ~n~

Vậy thì ta chỉ cần duyệt qua các ước ~i~ của ~n~ sao cho ~\large gcd(i, \frac{n}{i}) = 1~ và nhân tổng với ~n~. Độ phức tạp là ~\mathcal{O}(\sqrt{n} \cdot \mathcal{log}(n))~. Ta còn có thể cải tiến để bỏ qua phần kiểm tra ~\large gcd(i, \frac{n}{i})~, phần này xin nhường lại cho bạn đọc.


Comments

Please read the guidelines before commenting.



  • 0
    quoc14   commented on Nov. 22, 2022, 2:48 p.m.

    ad ơi em code như hướng dẫn vẫn bị sai 30 % test cuối ạ.