Description
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
3
1
2
50
Sample Output
Case 1: 0
Case 2: 2.00
Case 3: 3.0333333333
设dp[i]表示i变成1的期望次数,则
dp[i]=(SUM(dp[j])/k)+1,j为i的因子,k为其因子个数
然而当取其因子为1时,j=i/1=i,所以：dp[i]=((SUM(dp[j'])+dp[i])/k)+1,j'为i除开因子i的因子
整理：dp[i]=(SUM(dp[j'])+k)/(k-1)
记忆化搜索即可。
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> using namespace std; #define N 100000 double dp[N+10]; double dfs(int n) { if(n==1) return dp[n]=0; if(dp[n]!=-1) return dp[n]; int k=0; double s=0; for(int i=1;i*i<=n;i++) { if(n%i==0) { if(i*i!=n) { k+=2; if(i!=n) s+=dfs(i); if(n/i!=n) s+=dfs(n/i); } else { k+=1; if(i!=n) s+=dfs(i); } } } return dp[n]=(s+k)/(k-1); } int main() { for(int i=0;i<=N;i++) dp[i]=-1; int T,iCase=1; int n; scanf("%d",&T); while(T--) { scanf("%d",&n); dfs(n); printf("Case %d: %.10f ",iCase++,dp[n]); } return 0; }