LightOJ - 1038 Race to 1 Again

给一个数字，等概率选择一个这个数字的除数，然后将这个数字除以这个除数，直到这个数字等于1，求这个数字等于1的期望次数。

我们用  表示这个数字的期望次数，对于每一个数字 i ，有

，化简后得 

所以枚举每一个数字，暴力跑一下他的因数

#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
double dp[100005];
void init()
{
	for (int i = 2; i <= 100000; i++)
	{
		int cnt = 0;
		dp[i] += dp[1];
		cnt += 2;
		for (int j = 2; j <= sqrt(i); j++)
		{
			if (i % j == 0)
			{
				dp[i] += dp[j];
				cnt++;
				if (j != i / j)
				{
					dp[i] += dp[i / j];
					cnt++;
				}
			}
		}
		dp[i] = (dp[i] + cnt) / (cnt - 1);
	}
}
int main()
{
	init();
	int T, cas = 1;
	sc("%d", &T);
	while (T--)
	{
		int n;
		sc("%d", &n);
		printf("Case %d: %.9lf\n", cas++, dp[n]);
	}
}