ligntOj 1038(期望)

题意：给出一个n，一步操作是让n除n的一个随机因子得到新的n，问可以得到新的n是1的步数期望。
题解：因为n/1=n这种选择会造成循环，所以需要用到递推，令n变成1的步数期望是f[n]，比如n是2，f[2] = 1/2(f[2] + 1) + 1/2(f[1] + 1)，加1是因为2变成2也需要一步，那么移项后，f[2] = 2 + f[1] = 2 + 0 = 2。
从小到大打一个f的表。

#include <stdio.h>
#include <string.h>
#include <math.h>
const int N = 100005;
int n;
double f[N];

int main() {
    int t, cas = 1;
    scanf("%d", &t);
    f[1] = 0;
    for (int i = 2; i <= N; i++) {
        int cnt = 1, temp = sqrt(i);
        f[i] = 0;
        for (int j = 2; j <= temp; j++) {
            if (i % j == 0 && j * j != i) {
                cnt += 2;
                f[i] += f[j];
                f[i] += f[i / j];
            }
            else if (j * j == i) {
                cnt++;
                f[i] += f[j];
            }
        }
        f[i] += cnt + 1;
        f[i] /= cnt;
    }
    while (t--) {
        scanf("%d", &n);
        printf("Case %d: %.10lf\n", cas++, f[n]);
    }
    return 0;
}