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
3
1
2
50
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秒 ************************************************************************/;const double pi = acos(-1.0);const int inf = 0x3f3f3f3f;const double eps = 1e-15;LL;typedef pair <int, int> 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;}
，不敢面对自己的不完美，总是担心自己的失败，
