LightOJ 1038 概率dp

题意：给一个数n，每次除它的一个因子（等概率），问除到1的次数的期望是多少

题解：概率dp，对于一个数x,y是x的因子个数，因子是a1到ay，E(x)=(E(a1)+1)/y+...+(E(ay)+1)/y，复杂度O（nsqrt（n））

#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pi acos(-1.0)
#define ll long long
#define mod 1000000007
#define C 0.5772156649
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1
#define pii pair<int,int>

using namespace std;

const double g=10.0,eps=1e-12;
const int N=100000+10,maxn=200000+10,inf=0x3f3f3f3f;

double dp[N];
vector<int>v[N];
int main()
{
    for(int i=1;i<=100000;i++)
    {
        for(int j=1;j*j<=i;j++)
        {
            if(i%j==0)
            {
                v[i].pb(j);
                if(j*j!=i)v[i].pb(i/j);
            }
        }
    }
    for(int i=2;i<=100000;i++)
    {
        double te=0;
        for(int j=0;j<v[i].size();j++)
        {
            int x=v[i][j];
            te+=1+dp[x];
        }
        dp[i]=te/(v[i].size()-1);
    }
    int res=0,t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        printf("Case %d: %.10f
",++res,dp[n]);
    }
    return 0;
}
/********************

********************/