题意：给一个Ｎ，在不大于Ｎ的素数中选一个p，如果p是N的约数，则将N变为N/p。否则不变，问最后N变为１的次数的期望。
思路：设E[X]为x变成1的期望，num代表小于x的质数数量，num1代表小于x并且能被x整除的素数数量。
则有$E[X]=frac{1}{num}sum E[x/p]+frac{num-num1}{num}E[x]+1$
移项可得$E[x]=sum frac{1}{num1}E[x/p]+frac{num}{num1}$
注意这里不要直接从1到n的遍历，因为有很多数在n的变化中是不会出现的，变化是没有意义的。所以需要用到记忆化搜索。
甚至由于每个数的状态只和比自己小的数有关，所以记忆化数组都不需要清空，这一组用的状态下一组还能继续用。
#pragma GCC optimize (2) #pragma G++ optimize (2) #pragma comment(linker, "/STACK:102400000,102400000") #include<bits/stdc++.h> #include<unordered_map> #define rep(i,a,b) for(int i=a;i<=b;++i) #define dep(i,b,a) for(int i=b;i>=a;--i) #define clr(a,b) memset(a,b,sizeof(a)) #define pb push_back #define pii pair<int,int > using namespace std; typedef long long ll; ll rd() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } const int maxn=1000010; double dp[maxn]; vector<int >prime; int vis[maxn+10]; void get_prime(){ vis[1]=1; for(int i = 2; i <= maxn; ++i){ if(!vis[i]) prime.push_back(i); for(int j = 0; j < prime.size() && prime[j]*i <= maxn; ++j){ vis[i*prime[j]]=1; if(i%prime[j] == 0) break; } } } int n; double dfs(int x){ if(x==1)return 0; if(dp[x]>0)return dp[x]; double num=0,num1=0; for(int i=0;i< prime.size()&&prime[i]<=x;i++){ if(x%prime[i]==0){ num1++; dp[x]+=dfs(x/prime[i]); } num++; } dp[x]+=num; dp[x]/=num1; return dp[x]; } int main(){ get_prime(); int T,cat=1; cin>>T; while(T--){ cin>>n; printf("Case %d: %.10lf ",cat++,dfs(n)); } } /* 3 1 3 13 */