TOP

Light oj 1038 Race to 1 Again（概率dp）

2015-11-21 01:03:28 来源: 作者: 【大中小】浏览:1次

Tags：Light 1038 Race Again 概率

1038 - Race to 1 Again

PDF (English)

Statistics

Forum

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 thisD.

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

Case 1: 0

Case 2: 2.00

Case 3: 3.0333333333

PROBLEM SETTER: JANE ALAM JAN

设x有n个因子，dp[x] =(dp[i]+dp[j]+....+dp[k])*(1/n)+dp[n]*1/n+1; (i,j,k表示x的因子)

换一下就可以得到dp[x]的表达式了，

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
          
            #include
            #define L(x) (x<<1) #define R(x) (x<<1|1) #define MID(x,y) ((x+y)>>1) #define eps 1e-8 //typedef __int64 ll; #define fre(i,a,b) for(i = a; i 
            
             = a;i--) #define mem(t, v) memset ((t) , v, sizeof(t)) #define ssf(n) scanf("%s", n) #define sf(n) scanf("%d", &n) #define sff(a,b) scanf("%d %d", &a, &b) #define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c) #define pf printf #define bug pf("Hi\n") using namespace std; #define INF 0x3f3f3f3f #define N 100005 double dp[N]; int n; void inint() { int i,j,cnt; double temp; dp[1]=0; mem(dp,0); fre(i,2,N) { cnt=0; temp=0; for(j=1;j*j<=i;j++) if(i%j==0) { cnt++; temp+=dp[j]; if(j*j!=i) { temp+=dp[i/j]; cnt++; } } dp[i]=(temp+cnt)/(cnt-1); } } int main() { int i,j,t,ca=0; sf(t); inint(); while(t--) { sf(n); pf("Case %d: %.6lf\n",++ca,dp[n]); } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：你的C/C++程序为什么无法运行？揭..	下一篇：dubbo+spring+zookeeper之demo制作

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: