题目

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

Sample Output

Case 1: 0

Case 2: 2.00

Case 3: 3.0333333333

大意

给出一个数，每次随机处一个它的因子，求他变成1的期望次数。

题解

令 f[I] 表示i在f[i]此后变成1。

\[f[i] = \sum_{j|i} (f[j]+1) / k, (k = \sum_j [j|i])
\]

代码

#include<bits/stdc++.h>

#define repeat(a,b,c,g) for (int a=b,abck=(g>=0?1:-1);abck*(a)<=abck*(c);a+=g)

using namespace std;

double f[110000];

int main()

{

	f[1] = 0;

	for (int i=2;i<=100000;i++)

	{

		double tot = 0;

		int tp = -1;

		for (int j=1;j<=sqrt(i);j++)

		{

			if (i % j == 0)

			{

				tp ++, tot += f[j] + 1;

				if (j * j != i)

					tp ++, tot += f[i/j] + 1;

			}

		}

		f[i] = tot / tp;

	}

	int n;

	cin >> n;

	for (int i=1;i<=n;i++)

	{

		int tmp;

		cin >> tmp;

		printf("Case %d: %.7f\n",i,f[tmp]);

	}

}

巴特西

A - Race to 1 Again

题目

Input

Output

Sample Input

Sample Output

大意

题解

代码

最新文章

热门文章