Solutions of Beautiful number

Select solution language

Defylogicguy Created at 2 likes

### Tóm tắt đề bài Ta định nghĩa $x$ là một số đẹp khi $x$ chỉ có các ước là 3, 5, hoặc 7. Nhiệm vụ của chúng ta là tìm số đẹp thứ $k$. --- ### Hướng giải Gọi hàm $f(x)$ là số lượng số đẹp không vượt quá $x$. Bài toán trở thành việc tìm $x$ nhỏ nhất sao cho $f(x) \geq k$. Ta có thể tìm $x$ bằng cách dùng tìm kiếm nhị phân (binary search) từ $0$ tới $10^{15}$. Bây giờ, nhiệm vụ của chúng ta là tính hàm $f(x)$ một cách tối ưu. Ta có thể làm điều đó bằng cách sử dụng [nguyên lý bao hàm - loại trừ](https://wiki.vnoi.info/translate/he/Number-Theory-7). Công thức của $f(x)$ là:$$ f(x) = \left\lfloor \frac{x}{3} \right\rfloor + \left\lfloor \frac{x}{5} \right\rfloor + \left\lfloor \frac{x}{7} \right\rfloor - \left\lfloor \frac{x}{15} \right\rfloor - \left\lfloor \frac{x}{21} \right\rfloor - \left\lfloor \frac{x}{35} \right\rfloor + \left\lfloor \frac{x}{105} \right\rfloor $$