题目链接：http://lightoj.com/volume_showproblem.php?problem=1038

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 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 ≤ 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

 

---

PROBLEM SETTER: JANE ALAM JAN

题意：求n变成1的期望（n除以它的因子）

解析：dp[i]表示i的期望，dp[i] = (dp[i/xi] + dp[i/x2] + dp[i/x3] + ...... + dp[i] + 1 * num ) / num   (x1, x2,x3,......i)都是i的因子，一共num个因子， + 1 表示还有一步从xi到i，一个加了num个， 因子包括1和它自己，上面的式子是原始的式子，可以进一步推导变成dp[i] = (dp[i/x1] + dp[i/x2] + dp[i/x3] + ...+ num) / (num-1)

代码：

#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<vector> #include<queue> #include<map> #include<cmath> #define N 100009 using namespace std; const int INF = 0x3f3f3f3f; double dp[N]; void init() { dp[1] = 0; dp[2] = 2.00; for(int i = 3; i <= 100000; i++) { int k = sqrt(i), cnt = 0; double sum = 0; for(int j = 1; j <= k; j++) { if(i % j == 0) { cnt++; sum += dp[j]; if(i / j != j) cnt++, sum+= dp[i/j]; } } dp[i] = (sum + cnt) / (cnt - 1); } } int main() { init(); int t, cnt = 0, n; scanf("%d", &t); while(t--) { scanf("%d", &n); printf("Case %d: %f\n", ++cnt, dp[n]); } }