LightOJ 1038 - Race to 1 Again （给一个数，用这个数的因数除以这个数，直到为1时，求除的次数的期望。）（概率）...-白红宇

LightOJ 1038 - Race to 1 Again （给一个数，用这个数的因数除以这个数，直到为1时，求除的次数的期望。）（概率）...

阅读量：4704 次

发布时间：2019-06-10

本文共 643 字，大约阅读时间需要 2 分钟。

题意：

题意：给一个数，用这个数的因数除以这个数，直到为1时，求除的次数的期望。

　　设一个数的约数有M个，E[n] = (E[a[1]]+1)/M+(E[a[2]]+1)/M+...+(E[a[M]]+1)/M

　　一个数最大的约数是它自己。

　　则有，E[n] = (E[a[1]]+1)/M+(E[a[2]]+1)/M+...+(E[n]+1)/M

　　(M-1)*E[n]=E[a[1]]+E[a[2]]+...+E[a[M-1]]+M

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          #include
           
            #include
            
             #include
             
              using namespace std;#define INF 0x3f3f3f3f#define LL long long#define N 100006#define Lson rood<<1#define Rson rood<<1|1double dp[N];void Q(){ dp[1]=0; for(int i=2;i