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

题解-小猪佩奇玩游戏

一道似乎用 $map$ 水过的题目,然而比赛却只有 $60ptc$ 还是太菜了。

$step1$

反正我是手模 $[1,10]$ 的答案。然后发现大多数数的贡献都是 $1$ 少数是 $1/2$ 。但是看看样例怎么会有 $13.83333333$ 这些神奇的小数。于是大胆猜想是不是与这个数 $x$ 等于多少个 $n^{k}(k∈N^{+},2\leq k)$ ，于是就有了 $60ptc$ 的好成绩

#include <bits/stdc++.h>
using namespace std;
map<int,int>ma;
double ans[1000005];
inline int ksm(int a,int b) {
    int ret=1;
    while(b) {
        if(b&1) ret=ret*a;
        a=a*a;
        b>>=1;
    }
    return ret;
}
int main() {
    int T;
    for ( int i=2;i<=100;i++ ) 
        for ( int j=2;j<=40;j++ ) {
            int s=ksm(i,j);
            if(s>100000||s<0) break;
            ma[s]+=1;
        }
    ans[1]=1;
    for ( int i=2;i<=100000;i++ ) 
        ans[i]=ans[i-1]+(1/(1.0*(ma[i]+1)));//预处理答案
    scanf("%d",&T);
    for ( int i=1;i<=T;i++ ) {
        int x;
        scanf("%d",&x);
        printf("%.8lf\n",ans[x]);
    }
    return 0;
}

$step2$

比赛比完我听 $ldl$ 巨佬说他的暴力倒着写就是正解 $qwq$

其实现在的方法更简单。先用 $map$ 存储 $n^k$ 数然后遍历 $map$ 就可以了。最后再加上某些为 $1$ 贡献的数就可以了。

#include <bits/stdc++.h>
using namespace std;
#define int long long

int n,T;
map<int,int> ma;

signed main() {
  scanf("%lld",&T);
  while(T--) {
      scanf("%lld",&n);
      ma.clear();
      for ( int i=2;i*i<=n;i++ ) 
          for ( int j=i*i;j<=n;j*=i ) ma[j]++;
      double ans=0;
      ans=n-ma.size();
      for ( auto i:ma ) ans+=1.0/(i.second+1);
      printf("%.8lf\n",ans);
  }
  return 0;
}