问题描述

小蓝开了一家宠物店，最近有一种 X 病毒在动物之间进行传染，小蓝为了以防万一打算购买测试剂对自己的宠物进行病毒感染测试。

为了减少使用的测试剂数目，小蓝想到了一个好方法：将 N 个宠物平均分为若干组，使得每组恰好有 K 只宠物，这样对同一组的宠物进行采样并混合后用一个试剂进行检测，如果测试结果为阴性则说明组内宠物都未感染 X 病毒；如果是阳性的话则需要对组内所有 K 只宠物单独检测，需要再消耗 K 支测试剂（当 K=1 时，就没必要再次进行单独检测了，因为组内只有一只宠物，一次检测便能确认答案）。

现在我们已知小蓝的宠物被感染的概率为 p，请问 K 应该取值为多少才能使得期望的测试剂的消耗数目最少？如果有多个答案输出最小的 K。

解题思路

数学知识

我们根据数学知识可以有：

然后得出公式：

代码

N = int(input())
p = float(input())

# 每组分的人数
ans = 1

# 记录一共用的最少试剂数
min_cost = float('inf')

for K in range(1, N + 1):
    # 不能平均分
    if N % K != 0:
        continue
    # 一共用的试剂数
    cost  = (N // K) * (1 + K * (1 - (1 - p) ** K))
    if cost < min_cost:
        min_cost = cost
        ans = K
print(ans)