Lightoj 1038

题目：戳这里

题意：一个数字n不断迭代地除以自身的因子得到1。求这个过程中操作除法次数的期望。

解题思路：

求概率基本都是从一个最基础的状态开始延伸推出公式，得出答案。
因为每个数都有个共同的最终状态1，所以我们从1向n推（注意用到期望的可加性，可加性不需要事件相互独立。
可以推出期望公式：
E=1/n * 1 + (n - 1)/n *(1 + E1 + ... + En)
Ei表示D除以一个除数后值为Di时，Di的期望。（第一道自己ac的该类型题目，记录一下

附ac代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
const int inf = 0x3f3f3f3f;
const ll mod = 998244353;
double cnt[maxn];
double dp[maxn];
int main() {
    int t, n;
    dp[1] = 1.0;

    for(int i = 1; i <= maxn; ++i)
    {
        if(cnt[i])
        dp[i] /= cnt[i];
        for(int j = 2; j * i <= maxn; ++j)
        {
            dp[i * j] += dp[i] + 1.0;
            cnt[i * j] += 1.0;
        }
    }
    scanf("%d", &t);
    dp[1] = 0;
    for(int cas = 1; cas <= t; ++cas)
    {
        scanf("%d", &n);
        printf("Case %d: %f
", cas, dp[n]);
    }

    return 0;
}