内存很小，跑得不算慢（主要是码量小）

评测记录（峰值时间85ms，峰值内存552 KiB）

#include<bits/stdc++.h>
using namespace std;
const double e=1e-7;
#define N 1001
double f[N];int k,q,i,j,d,p,s[N];
int main()
{
	scanf("%d%d",&k,&q);f[1]=1.0;
	for(i=2,d=0;d<N;i++)
	{
		for(j=k;j;j--)f[j]=1.0*(k-j+1.0)/k*f[j-1]+1.0*j/k*f[j];
		while(f[k]>=((d-e)/2000.0)&&d<N)s[d++]=i;
	}
	for(i=1;i<=q;i++){scanf("%d",&p);printf("%d\n",s[p]);}
	return 0;
}

这是一篇洛谷题解，内存略大一些，但跑得很快

提交记录（峰值时间30ms，峰值内存868 KiB）

#include <bits/stdc++.h>
using namespace std;
const long double EPS = 1e-8;
const int MAX = 1e3 + 7;
long double dp[MAX];
long double ans[MAX << 3];
//楼上大佬已经证过，最大的期望天数跑不出 1000*ln(1000) 
//这里用*8 代替 *ln(1000)
int main()
{
	int K, M;
	cin >> K >> M;
	dp[0] = 1.0;
	for (int i = 1; i <= 8000; i++)
	{
		for (int j=K;j>0;j--)//倒序扫
		{
			dp[j]=(dp[j-1]*(K-j+1)+dp[j]*j)/(K*1.0);
            //转移
		}
		ans[i] = dp[K];//记录 dp[k]
		dp[0] = 0;
	}
	while (M--)
	{
		int p;
		cin >> p;
		for (int i = 1; i <= 8000; i++)
		{
			if (ans[i] * 2000 >= p - EPS)//防炸精写法
			{
				cout << i << "\n";
				break;
			}
		}
	}
}