[UVA][概率DP] 11762 - Race to 1＠Morris' Blog｜PChome Online 人新台

Morris' Blog 我在摸索我存在的意、生命的意、涵及值。有真正神手般的害，套用模式是大部分的情。那害的我存在的意何，托出神的存在？有候不能怪人不我，我已始省思，什我有人的原因，而是全要靠人。有候我我不同，那是因我做不到很多人能到的事情。我不到、玩不起、得不明、理解得不多，我缺少的文能力，就是一切一切能的判定。此，我不得能做些人有助的事情。我知道我自己是不服的性格，但在我不得不。我有能力，因此我必。我到底世界作什？充不定性，而我是法出拔萃，想一般人似乎也回不了了。越大的挑需要越力的支持，而我的支持是什？最近人，但都是失的局，人能接受，不需要言，不需要通，一切所想都表不出。
49的鼓 6站台

2013-10-06 20:43:53| 人1,608| 回0 | 上一篇 | 下一篇

[UVA][概率DP] 11762 - Race to 1

推 0 收藏 0 0 站台

Race to 1

Input: Standard Input

Output: Standard Output

Dilu have learned a new thing about integers, which is - any positive integer greater than 1 can be divided by at least one prime number less than or equal to that number. 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 prime number less than or equal to D. If D is divisible by the prime number then he divides D by the prime number to obtain new D. Otherwise he keeps the old D. He repeats this procedure until D becomes 1. What is the expected number of moves required for N to become 1.

[We say that an integer is said to be prime if its divisible by exactly two different integers. So, 1 is not a prime, 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 of the next T lines will contain one integer N (1 <= N <= 1000000).

Output

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

Sample Input Output for Sample Input

Case 1: 0.0000000000

Case 2: 2.0000000000

Case 3: 6.0000000000

Problemsetter: Md. Arifuzzaman Arif

Special Thanks: Sohel Hafiz

目描述：

一字 N， [2, N] 挑一 p，如果 N%p = 0，N = N/p。求次的期望值。

目解法：

很久概率 DP 了，由於有一次可能一次不。

dp[n] = p0*dp[n] + 1 + sigma(p1*dp[n/prime_factor]);

移之後便可以得到公式。

其中 p0 表示到因的率，p1 表示每因到的率。

#include <stdio.h>
#include <string.h>
#include <vector>
#define maxL (1000000>>5)+1
#define GET(x) (mark[x>>5]>>(x&31)&1)
#define SET(x) (mark[x>>5] |= 1<<(x&31))
using namespace std;
int mark[maxL];
vector<int> pfactor[1000005];
int psum[1000005] = {};
double dp[1000005];
char used[1000005] = {};
void sieve() {
   register int i, j, k;
    SET(1);
    int n = 1000000;
    for(i = 2; i <= n; i++) {
       psum[i] = psum[i-1];
        if(!GET(i)) {
           psum[i]++;
           pfactor[i].push_back(i);
           for(j = i+i; j <= n; j += i) {
               SET(j);
               pfactor[j].push_back(i);
           }
        }
    }
}//d[n]=p0*d[n]+1+p1*d[n/d1]+p1*d[n/d2]...
double dfs(int n) {
   if(n == 1)   return 0;
   if(used[n])   return dp[n];
   used[n] = 1;
   double p0, p1, e = 0;
   p0 = 1-(double)pfactor[n].size()/psum[n];
   p1 = 1.0/psum[n];
   for(int i = pfactor[n].size()-1; i >= 0; i--)
       e += dfs(n/pfactor[n][i])*p1;
   e = (e+1)/(1-p0);
   dp[n] = e;
   return e;
}
int main() {
   sieve();
   int testcase, n, cases = 0;
   scanf("%d", &testcase);
   while(testcase--) {
       scanf("%d", &n);
       printf("Case %d: %.10lf\n", ++cases, dfs(n));
   }
   return 0;
}