MATH - Chính phương lớn nhất 02

Đề bài

Trong một phòng nghiên cứu toán học, có các thẻ số được đánh số lần lượt từ \(1\) đến \(N\). Mỗi thẻ chỉ được sử dụng nhiều nhất một lần.

Nhà nghiên cứu được phép chọn một tập con gồm các thẻ số nguyên dương phân biệt. Gọi \(P\) là tích các số ghi trên những thẻ được chọn.

Một cách chọn được gọi là hoàn hảo nếu \(P\) là một số chính phương.

Ký hiệu \(F(N)\) là giá trị lớn nhất của \(P\) trong tất cả các cách chọn hoàn hảo từ các thẻ mang số từ \(1\) đến \(N\).

Cho một số nguyên dương \(X\). Hãy tìm số nguyên dương nhỏ nhất \(N\) sao cho

\(F(N)\ge X\).

Chỉ xét các giá trị \(1\le N\le 10^7\).

Nếu không tồn tại giá trị \(N\) thỏa mãn thì in ra -1.

Dữ liệu vào

Một dòng duy nhất chứa số nguyên dương \(X\).

Dữ liệu ra

In ra số nguyên dương nhỏ nhất \(N\) sao cho \(F(N)\ge X\).

Nếu không tồn tại thì in ra -1.

Ràng buộc

• \(1\le X\le 10^{18}\).
• Chỉ xét \(1\le N\le 10^7\).
• Mỗi số trong tập \(\{1,2,\ldots,N\}\) chỉ được chọn nhiều nhất một lần.

Subtask

• Subtask 1 (20%): \(X\le 10^6\).
• Subtask 2 (30%): \(X\le 10^{12}\).
• Subtask 3 (50%): Không có ràng buộc nào khác.

Sample Input 1

100

Sample Output 1

6

Sample Input 2

500

Sample Output 2

8

Giải thích

Ở ví dụ thứ nhất, với \(N=5\), tích chính phương lớn nhất có thể tạo được là \(4\), nên chưa đạt ngưỡng \(100\).

Với \(N=6\), có thể chọn các thẻ \(\{2,3,4,6\}\), khi đó

\(P=2\cdot3\cdot4\cdot6=144\),

là số chính phương và \(144\ge100\), do đó đáp án là \(6\).

Ở ví dụ thứ hai, với \(N=7\), tích chính phương lớn nhất có thể tạo được là \(144\), nên chưa đạt ngưỡng \(500\).

Với \(N=8\), có thể chọn các thẻ \(\{3,4,6,8\}\), khi đó

\(P=3\cdot4\cdot6\cdot8=576\),

là số chính phương và \(576\ge500\), vì vậy đáp án là \(8\).