传送门:http://www.lightoj.com/volume_showproblem.php?problem=1038
题目 / Problem
有T组用例。给定一个正整数N(1 <= N <= 1e5),每次N可以等概率得除以一个因子,从而变成一个新的N,问从N变到1的次数期望。
次数期望是说,假如现在是第 i 轮变换,那么这一次(x - > y)对于结果的贡献是i * p(x -> y),p(x -> y)为 x 变换到 y 的概率。
思路 / Thought
用f[i]表示从i变换到1的次数期望,从前往后推。
假设现在要求f[x],那么先求出x的因子,复杂度为O(sqrt(x)),设因子分别为a1,a2,a3.....am,不难发现a1 == 1, am == x。
那么现在x变成任意一个因子的概率为1 / m,现在假设路线为x -> a1 -> ... -> 1,那么期望为1 / m * (1 + f[a1]),也就是说有1 / m的概率,通过走(1 + f[i])步到达点1。
整理一下得到

然后把f(x)放一边,得到

预处理一下就可以了。
代码 / Code
/*Copyright (C) Eriktse 2022*/ #include <bits/stdc++.h> #define pb push_back #define fi first #define se second #define int long long using namespace std; inline int readInt() { int s = 0, w = 1;char ch = getchar(); for(;ch < '0' || ch > '9';ch = getchar())if(ch == '-')w = -1; for(;'0' <= ch && ch <= '9';ch = getchar())s = s * 10 + ch - '0'; return s * w; } const int maxn = 1e5 + 9; double f[maxn]; int kase = 1; vector<int> getyz(int x) { vector<int> res; for(int i = 1;i <= x / i; ++ i) { if(x % i == 0) { res.pb(i); if(i * i != x)res.pb(x / i); } } return res; } void init(int N) { f[1] = 0; for(int x = 2;x <= N; ++ x) { vector<int> yz = getyz(x); double sum = 0; for(auto i : yz)sum += f[i]; int m = yz.size(); f[x] = (sum + m) / (m - 1); } } signed main() { init(maxn - 5); int T = readInt(); while(T --) { int x = readInt(); printf("Case %lld: %.8lf\n",kase ++, f[x]); } return 0; }
Comments NOTHING