UVA - 11762 Race to 1

Dilu have learned a new thingabout integers, which is - any positive integer greater than 1 can be divided byat least one prime number less than or equal to that number. So, he is nowplaying with this property. He selects a number N. And he calls this D.

In each turn he randomly chooses aprime number less than or equal to D.If D is divisible by the prime numberthen he divides D by the primenumber to obtain new D. Otherwise hekeeps the old D. He repeats thisprocedure until D becomes 1. What isthe expected number of moves required for Nto become 1.

[We say that an integer is said tobe prime if its divisible by exactly two different integers. So, 1 is not aprime, by definition. List of first few primes are 2, 3, 5, 7, 11, …]

Input

Input will start with an integer T (T <= 1000), which indicates the number of test cases. Each ofthe next T lines will contain oneinteger N (1 <= N <= 1000000).

Output

For each test case output a single line giving the casenumber followed by the expected number of turn required. Errors up to 1e-6 willbe accepted.

SampleInput Outputfor Sample Input

3

1

3

13

Case 1: 0.0000000000

Case 2: 2.0000000000

Case 3: 6.0000000000

Problemsetter: Md. Arifuzzaman Arif

Special Thanks: Sohel Hafiz

題意：給你一個整數N，每次都可以在不超過N的素數中隨機選擇一個P，如果P是N的約數，則把N變成N/P，否則N不變，問平均情況下要多少次隨機選擇，才能把N變成1

思路：設f(i)表示當前的數為i時接下來需要選擇的次數，這樣我們就能得到一個方程，例如：f(6)=1+f(6)+1/3+f(3)*1/3+f(2)*1/3

我們設不超過x的素數有p(x)個，其中有g(x)個是x的因子，則f(x) = 1 + f(x)*(1-g(x)/p(x)) + f(x/y)/p(x){y是x的素因子}，移項後整理得f(x)=(f(x/y)+p(x))/g(x){y是x的因子}，因為

x/y

#include 
#include 
#include 
#include 
typedef long long ll;
using namespace std;
const int maxn = 1000005;
const int maxm = 100000;

double f[maxn];
int prime[maxm], cnt, vis[maxn];

void init() {
	memset(vis, 0, sizeof(vis));
	cnt = 0;
	f[0] = f[1] = 1;
	for (ll i = 2; i < maxn; i++) 
		if (!vis[i]) {
			prime[cnt++] = i;
			for (ll j = i*i; j < maxn; j += i)
				vis[j] = 1;
		}
}

double dp(int x) {
	if (x == 1)
		return 0.0;
	if (vis[x])
		return f[x];
	vis[x] = 1;
	double &ans = f[x];
	int g = 0, p = 0;
	ans = 0;
	for (int i = 0; i < cnt && prime[i] <= x; i++) {
		p++;
		if (x % prime[i] == 0) {
			g++;
			ans += dp(x / prime[i]);
		}
	}
	ans = (ans + p) / g;
	return ans;
}

int main() {
	init();
	memset(vis, 0, sizeof(vis));
	int t, n, cas = 1;
	scanf("%d", &t);
	while (t--) {
		scanf("%d", &n);
		printf("Case %d: %.10f\n", cas++, dp(n));
	}
	return 0;
}