推荐原文阅读
$\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$的集合的期望删除次数,其它数组是线性筛里面的
//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;
}
Comments | 1 条评论
评论测试
