题意

\(T\in[1,10^4]\)组数据，每组给定一个数字\(n\in[1,10^5]\)。\(n\)每次除以\(n\)的一个因子，商记为新的\(n\)。求\(n\)被除到\(1\)的期望次数，答案允许\(10^{-6}\)以内的误差。

解法

预处理出\([1,10^5]\)以内的所有\(n\)的期望，离线查询。

对于每个数\(n\)，可以累加其因子的期望次数，然后除去\(n\)的因子数再\(+1\)，记为\(n\)的期望次数。

原理

显然选中任何一个因子是等概率事件。

记\(x\)被除到\(1\)的期望次数为\(E(x)\)，\(n\)的因子为\(a_i\)，选中\(a_i\)的概率为为\(P(A_i)\)，则\[E(n)=\sum\limits_{a_i}\{[E(a_i)+1]P(A_i)\}\]。若记\(n\)的因子数为\(fac\)，则由上式可得\[E(n)=\frac{\sum\limits^{fac}[E(a_i)+1]}{fac}=\frac{\sum\limits^{fac}E(a_i)}{fac}+1\]。若因子按大小排序，则最后一个因子必定是自身，即\[E(n)=\frac{\sum\limits^{fac-1}E(a_i)+E(n)}{fac}+1\]，移项得\[E(n)=\frac{\sum\limits^{fac-1}E(a_i)+fac}{fac-1}\]。

反思

学术须严谨。宁可煮久一些，也不可吃夹生饭。

代码

#include
    
     #include
     
      #include
      
       #define reg register intusing namespace std;const int LIM = 1e5;double dp[LIM + 1];int main(){    for(reg i = 2; i <= LIM; ++ i){        double num = 0, ans = 0;        for(reg j = 1; j * j <= i; ++ j){            if(i % j == 0){                ++ num;                ans += dp[j];                if(j != i / j){ // 此处由于dp[i]还未计算，所以不特判i / j == i不影响答案。                    ++ num;                    ans += dp[i / j]; // 同理                 }            }            dp[i] = (ans + num) / (num - 1); // 经化简的公式        }    }    int T, Case = 0; scanf("%d", & T);    while(T --){        int n;        scanf("%d", & n);        printf("Case %d: %.6f\n", ++ Case, dp[n]);    }    return 0;}