首页 > 代码库 > LightOJ 1038 Race to 1 Again 期望 记忆化dp

LightOJ 1038 Race to 1 Again 期望 记忆化dp

2024-07-18 02:49:16   225人阅读

题目链接：点击打开链接

1038 - Race to 1 Again
PDF (English)StatisticsForum
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 ≤ 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

3

1

2

50

Case 1: 0

Case 2: 2.00

Case 3: 3.0333333333

 

写出方程后发现是 dp[n] = *** + dp[n]*C ，

然后把dp[n]移到一边，就是一个普通的递推式。

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<cstring>

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;
}


联系
我们