LightOJ

给你一个N (1 ≤ N ≤ 10⁵)　每次N都随机选一个因子d，然后让N=N/d， 求N变成1的次数的期望；

题目链接

#include <bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
const int N = 1e5+7;
double dp[N];
int main(){
//    ios::sync_with_stdio(false);
//    cin.tie(0);
    int t;
    scanf("%d",&t);
    int w=0;
    for(int i=2;i<N;i++){
        int cnt=0; double sum=0;
        for(int j=1;j<=sqrt(i);j++){
            if(i%j==0){
                cnt++;
                sum+=(dp[j]+1);
                if(i/j!=j){
                    cnt++;
                    sum+=(dp[i/j]+1);
                }
            }
        }
        dp[i]=sum/(cnt-1);
    }
    while(t--){
        int n;
        scanf("%d",&n);
        printf("Case %d: %.10f
",++w,dp[n]);
    }
}