LightOJ 1038 Race to 1 Again 期望 記憶化dp

題目鏈接：點擊打開鏈接

1038 - Race to 1 Again PDF (English) Statistics Forum Time Limit: 2 second(s) Memory Limit: 32 MB

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 Dbecomes 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 ≤ 10⁵).

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

3

1

2

50

Case 1: 0

Case 2: 2.00

Case 3: 3.0333333333

寫出方程後發現是 dp[n] = *** + dp[n]*C ，

然後把dp[n]移到一邊，就是一個普通的遞推式。

#include
#include
#include
#include

using namespace std;
#define N 100005
double dp[N];
int main()
{
    dp[1] = 0;
    dp[2] = 2;
    for(int i = 3; i < N; i++) {
        dp[i] = 0;
        int tmp = 0;
        for(int j = 1; j*j <= i; j++)
        {
            if(i % j == 0)
            {
                dp[i] += dp[j];
                tmp++;
                if(j != i/j && i/j != i)
                {
                    dp[i] += dp[i/j];
                    tmp++;
                }
            }
        }
        dp[i] = ( dp[i] + tmp+1)/tmp;
    }
    int n, Cas=1, T, i; scanf("%d",&T);
    while(T--)
    {
        scanf("%d", &n);
        printf("Case %d: %.10f\n", Cas++, dp[n]);
    }
    return 0;
}