程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> Light oj 1038 Race to 1 Again（概率dp）

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

編輯：關於C++

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;
}