Problem Description

Xiaolan opened a pet shop. Recently, an X virus has been spreading among animals. To be safe, Xiaolan plans to buy test kits to test his pets for infection.

To reduce the number of test kits used, Xiaolan came up with a good idea: evenly divide $N$ pets into several groups, so that each group has exactly $K$ pets. For each group, take samples from the pets in the same group, mix them, and use one test kit to test. If the test result is negative, it means none of the pets in the group is infected with the X virus. If it is positive, then all $K$ pets in the group need to be tested individually, which will consume an additional $K$ test kits (when $K=1$, there is no need for another individual test, because there is only one pet in the group, and one test is enough to confirm the result).

Now we know that the probability that Xiaolan’s pets are infected is $p$. What value should $K$ take so that the expected number of test kits consumed is minimized? If there are multiple answers, output the smallest $K$.

Input Format

The first line contains an integer $N$.

The second line contains a floating-point number $p$.

Output Format

Output one line containing an integer $K$ as the answer.

1000
0.05

5

Hint

【Test Case Scale and Constraints】

For $30\%$ of the test cases: $1\leq N\leq 10$.

For $60\%$ of the test cases: $1\leq N\leq 1000$.

For $100\%$ of the test cases: $1\leq N\leq 10^6$，$0\leq p\leq 1$。

Translated by ChatGPT 5