Race to 1 Again

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

3

1

2

50

Sample Output

Case 1: 0

Case 2: 2.00

Case 3: 3.0333333333

题目大意是,给你一个数N,可以选择一个1~N里的数且是N的约数D,将N/=D,接着循环着做,知道N=1,求完成目标的期望步数.

设数N的期望为E[N],则:

E[n]=E[a[1]]/cnt+E[a[2]]/cnt+...+E[a[cnt]]/cnt+1

而因为a[cnt]就是n,所以设E[a[1]]/cnt+E[a[2]]/cnt+...+E[a[cnt-1]]/cnt=S

则E[n]=(S+E[n])/cnt+1;解得E[n]=(S+cnt)/(cnt-1)注意,E[1]就等于0哦.

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<cmath>
 5 using namespace std;
 6 int n;
 7 double E[100005];
 8 int main(){
 9     memset(E,0,sizeof E),E[1]=0,E[2]=2;
10     for (int i=3; i<=100000; i++){
11         double sumE=0,num=0;
12         for (int j=1; j<=sqrt(i); j++) if (i%j==0) sumE+=E[j],num++,sumE+=E[i/j]*(j*j!=i),num+=(j*j!=i);
13         E[i]=(sumE+num)/(num-1);
14     }
15     int T; scanf("%d",&T);
16     for (int Ts=1; Ts<=T; Ts++){
17         scanf("%d",&n);
18         printf("Case %d: %.10lf\n",Ts,E[n]);
19     }
20     return 0;
21 }

View Code

[LightOJ 1038] Race to 1 Again