题解 P5589 【小猪佩奇玩游戏】

· · 题解

这是一篇乱搞的题解（

首先，对于1个数x，如果有a个数的超过1的正整数次幂是它，那么它对答案的贡献就是\frac{1}{a+1}

简单证明：选取了这个数，那么在这之前就没有选取这a个数中的任何一个，相当于a+1个人排队，x在队首的概率，显然就是\frac{1}{a+1}

另外，\sum\limits_{i=1}^{log_2n}\sqrt[i]{n}是\sqrt{n}级别的，所以可以感性理解能被影响的数是很少的。

吹了这么多水，我只是想表达一个想法：

乱 搞 可 过

我们直接对于1,2,3...\sqrt{n}的数，枚举它的次幂，然后直接暴力计算贡献即可。我们需要记录一个数是几个数的正整数次幂，前文说了被影响的数很少，所以直接放入map中即可。普通map的复杂度是O(T\sqrt{n}logn)，想要获得满分需要使用unordered_map。

#include<tr1/unordered_map>
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define MX 1000000000
#define ld long double
int T,n;
ld P[100005];
tr1::unordered_map<int,int>att;
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for(int i=2;i*i<=n;++i)P[i]=1;
        ld sum=n;//初始所有数的贡献都设定为1
        att.clear();
        for(int i=2;i*i<=n;++i){
            LL tmp=i;
            for(int mi=2;mi<=32;++mi){//2^30大于1e9，所以枚举到30就行了
                tmp=tmp*i;
                if(tmp>n)break;//大于n直接跳过
                sum+=(1.0-1.0/(1+att[tmp]));
                //因为之前计算过这个数的贡献了，所以我们需要先减去这个数的贡献，再加上新的贡献
                att[tmp]++;
                sum-=(1.0-1.0/(1+att[tmp]));
                //因为我们默认贡献为1，所以这里的贡献定义为期望花费比1小多少
            }
        }
        printf("%.8Lf\n",sum);
    }
    return 0;
}