题解 P5589 【小猪佩奇玩游戏】
LRL52
2019-10-16 17:39:40
推荐[原文阅读](https://www.luogu.org/blog/lrl/solution-p5589)
> $\Theta(T\log^2 n)$的解法，~~搞了我半个下午才弄出来~~
> 蒟蒻的我反复看了几遍视频讲解，并经过反复推敲，终于弄懂了$\log^2$的做法
> 以下题解主要是对$memset0$巨佬题解的补充说明，尤其是高能部分，这里重点讲解**具体如何计算大小为$i$的集合个数**，至于计算删除大小为$i$的集合的期望次数可以见其它题解，已经讲的很清楚了
- $\sqrt n$的做法，复杂度的瓶颈在于计算有**多少个大小为$i$的集合**
- **大小为$i$的集合应该是$\lfloor n^{\frac{1}{i} }\rfloor$个**，考虑集合中最小的数字$x$，那么$x^i \le n$, 则$x \le \lfloor n^{\frac{1}{i} }\rfloor$
- 由于$1^{\text{任意次方}} = 1$, 所以$1$提出来单独计算，故上面计算出的**个数还要再$-1 $**
- 表示我们可以把$2 \sim x$的数作为那些集合的**首项(集合中最小的元素)**, 例如$i = 2, x = 4$, 那么集合就有$\text{\{2, 4\}, \{3, 9\}, \{4, 16\}}$
- 但是我们发现，其实像$\{2, 4\}, \{4, 16\}$的集合**不一定是极大的**，它可能被包含在$\{2, 4, 8, 16\}$这样的集合中
- **不是极大的集合意味着它可以扩张到更大的集合，而且它不是独立的，与外部有连边**
- 为了**去除那些不合法的集合(不是极大的集合)**, 问题转化为如何计算**一个集合被更大的集合包含了多少次**，我们要从答案中**减掉**这些不合法的贡献
- 对于一个确定的集合$S$，该集合的大小为$a$, 最小元素为$x$, 设较小集合的大小为$b$, 在较大集合中出现了$k$次($k$即是我们想求的)， 我们考虑**较小集合的首项(较小集合中最小的元素)** $y = x^k(y \in S)$， 例如$S = \{2, 4, 8, 16\}$，则$a = 4, x = 2$，当$b = 2$时，$y = 2, 4$
- 可知较小集合的最大元素是$y^b$, 并且由于$y^b \in S$, 则
$$y^b \le x^a$$
$$x^{kb} \le x^a$$
$$kb \le a$$
$$k \le \lfloor \frac{a}{b} \rfloor$$
- 不难发现$k$**这个值只和两个集合的大小有关**, 因此对于大小为$a$的较大集合, **设该集合有$tot$个**，那么对于大小为$b(b < a)$的较小集合, 它会在大小为$a$的集合中出现$tot \times \lfloor \frac{a}{b} \rfloor$个，这些贡献是不合法的，应该**减掉**
- 在实现程序中为了**避免重复减掉同样的贡献**，可以用**倒序循环实现**，具体见程序
- 这题毒瘤卡精度，$pow$会因为精度$WA \ \ 1$个点，可以使用二分 $+ $快速幂代替$pow$函数
> 以下程序可以处理$n \le 10^{18}$的数据，$d[i]$表示$i$的约数个数（使用线性筛实现，只是为了复习下）, $f[i]$和$g[i]$分别表示大小为$i$的集合的**个数**，和大小为$i$的集合的**期望删除次数**，其它数组是线性筛里面的
```cpp
//ID: LRL52 Date: 2019.10.16
#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
#include<bits/stdc++.h>
using namespace std;
const int N = 1055, M = 2055; char ss[1 << 21], *A = ss, *B = ss, cc;
inline char gc(){return A == B && (B = (A = ss) + fread(ss, 1, 1 << 21, stdin), A == B) ? EOF : *A++;}
template<class T>inline void rd(T &x){
int f = 1; x = 0, cc = gc(); while(cc < '0' || cc > '9'){if(cc == '-') f = -1; cc = gc();}
while(cc >= '0' && cc <= '9'){x = x * 10 + (cc ^ 48); cc = gc();} x *= f;
}
#define int long long
#define double long double
int Pcnt, n;
int d[75], vm[75], prime[75], vm2[75], f[75], h[75];
double g[75], Res;
void Prework(){
d[1] = 1;
rep(i, 2, 65){
if(!vm[i]){
vm[i] = vm2[i] = i, prime[++Pcnt] = i;
d[i] = 2;
}
rep(j, 1, Pcnt){
if(prime[j] > vm[i] || prime[j] > 65 / i) break;
int x = i * prime[j];
vm[x] = prime[j];
if(i % prime[j]){
vm2[x] = prime[j];
d[x] = d[i] * d[prime[j]];
}
else{
vm2[x] = vm2[i] * prime[j];
if(x == vm2[x]) d[x] = d[i] + 1;
else d[x] = d[x / vm2[x]] * d[vm2[x]];
}
}
}
g[1] = 1.0;
rep(i, 2, 65) g[i] = g[i - 1] + 1.0 / d[i];
}
int qp(int a, int k){
int ret = 1; double _a = a;
Res = 1.0;
while(k){
if(k & 1) ret = ret * a, Res = Res * _a;
a = a * a;
_a = _a * _a;
k >>= 1;
}
return ret;
}
int calc(int n, int k){
int l = 1, r = n;
while(l <= r){
int mid = (l + r) >> 1;
if(qp(mid, k) > n || Res > 1e18) r = mid - 1;
else l = mid + 1;
}
return r;
}
#undef int
int main(){
#define int long long
Prework();
int Task; rd(Task);
while(Task--){
rd(n);
if(n == 0){
puts("0.00000000");
continue;
}
double ans = 1.0;
int up = n;
rep(i, 1, n){
//h[i] = pow(n, 1.0 / i);
h[i] = calc(n, i); //calc n^(1/i)
--h[i];
if(h[i] == 0){
up = i - 1;
break;
}
}
for(int i = up; i >= 1; --i){
f[i] = h[i];
rep(j, i + 1, up)
f[i] -= (j / i) * f[j];
}
rep(i, 1, up) ans += f[i] * g[i];
printf("%.8Lf\n", ans);
}
return 0;
}
```