LIghtOJ1038---Race to 1 Again(概率dp) - c++编程基础

Rimi learned a new thing about integers, which is - any positive integer greater than 1 can be divided by its divisors. So, he is now playing with this property. He selects a number N. And he calls this D.

In each turn he randomly chooses a divisor of D (1 to D). Then he divides D by the number to obtain new D. He repeats this procedure until D becomes 1. What is the expected number of moves required for N to become 1.
Input

Input starts with an integer T (≤ 10000), denoting the number of test cases.

Each case begins with an integer N (1 ≤ N ≤ 105).
Output

For each case of input you have to print the case number and the expected value. Errors less than 10-6 will be ignored.
Sample Input

Output for Sample Input

Case 1: 0

Case 2: 2.00

Case 3: 3.0333333333

Problem Setter: Jane Alam Jan

dp[i]表示把i变成1的期望次数

/*************************************************************************
    > File Name: c.cpp
    > Author: ALex
    > Mail: zchao1995@gmail.com 
    > Created Time: 2015年04月29日 星期三 19时40分52秒
 ************************************************************************/

#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include
              #include 
              
                #include 
               
                 #include 
                
                  using namespace std; const double pi = acos(-1.0); const int inf = 0x3f3f3f3f; const double eps = 1e-15; typedef long long LL; typedef pair 
                 
                   PLL; double dp[100110]; double dfs(int num) { if (dp[num] != -1) { return dp[num]; } int cnt = 2; double ans = 0; for (int i = 2; i * i <= num; ++i) { if (num % i == 0) { ++cnt; ans += dfs(num / i); if (num / i != i) { ans += dfs(i); ++cnt; } } } ans += cnt; ans /= (cnt - 1); return dp[num] = ans; } int main() { int t; scanf("%d",&t); int icase = 1; while (t--) { int n; scanf("%d", &n); for (int i = 1; i <= n; ++i) { dp[i] = -1; } dp[1] = 0; printf("Case %d: %.12f\n", icase++, dfs(n)); } return 0; }