传送门：>出错啦<
题意：给你一个整数n，每一次可以随机选择一个n的因子x（包括1和它自己），让n除以x——不停重复此过程，直到n==1. 问n被除到1的期望次数。
解题思路：
今天刚学的期望Dp，这道题就算入门啦，顺带总结一下期望Dp的做题方法。
一般的，我们可以设$f[i]$表示从状态i到目标状态的期望次数。因此我们可以先确定本题的目标状态——n变为1. 因此在本题中，我们可以设$f[i]$表示$n==i$时到$n==1$的期望次数。由于目标状态本身到目标状态是根本不用变的，因此先确定$f[1] = 1$
于是由于最小的已经确定了，我们可以从1开始推：由小的来确定大的。因此我们可以枚举i，再枚举i的所有因子。设i的因子为$a_1, a_2, ..., a_m$，则有：$$f[i] = \frac{f[a_1] + f[a_2] + ... + f[a_m]}{m} + 1$$
即f[i]可以通过除一次来得到所有的这些因子（是得到这些因子，并不是除掉，想一想为什么），因此$f[i]$变成1的期望就是它变成的所有这些因子的期望的平均值，再加上本次的这个1.
然而很快会发现，$a_m = i$，$f[i]$总不可能用自己来转移自己吧……因此我们需要对方程进行变形
一般处理期望这些问题的用得都是实数，所以可以当代数式来做：
两边同时乘以$m$，$$f[i] * m = f[a_1] + f[a_2] + ... + f[i] + m$$ $$f[i] * (m - 1) = f[a_1] + f[a_2] + ... + f[a_{m-1}] + m$$ $$f[i] = \frac{f[a_1] + f[a_2] + ... + f[a_{m-1}] + m}{m - 1}$$
Code
要注意的是，直接$O(n^2)$枚举会超时，所以我们可以$O(n\sqrt{n})$，再$O(\sqrt{n})$的时间内搞出所有因子——特判一下完全平方数即可
/*By QiXingzhi*/
#include <cstdio>
#include <cmath>
#include <queue>
#define r read()
#define Max(a,b) (((a)>(b)) ? (a) : (b))
#define Min(a,b) (((a)<(b)) ? (a) : (b))
using namespace std;
typedef long long ll;
const int INF = ;
inline int read(){
int x = ; int w = ; register int c = getchar();
while(c ^ '-' && (c < '' || c > '')) c = getchar();
if(c == '-') w = -, c = getchar();
while(c >= '' && c <= '') x = (x << ) +(x << ) + c - '', c = getchar();
return x * w;
}
int T,Case,N;
double f[];
inline void Solve(int N){
f[] = 0.0;
double m = 0.0, K = 0.0;
double flg = -1.0;
for(int i = ; i <= N; ++i){
K = 0.0;
m = 0.0;
flg = -1.0;
for(int j = ; j <= floor(sqrt(i)); ++j){
if(i % j == ){
m += 1.0;
K += f[j];
if(i % (i/j) == ){
m += 1.0;
K += f[i/j];
if(i/j == j){
flg = f[j];
}
}
}
}
if(flg != -1.0){
K -= flg;
m -= 1.0;
}
f[i] = (double)(K + m) / (double)(m - );
}
}
int main(){
Solve();
T = r;
while(T--){
N = r;
++Case;
printf("Case %d: %.8lf\n",Case, f[N]);
}
return ;
}