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

题解-小猪佩奇玩游戏

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

• 

  反正我是手模的答案。然后发现大多数数的贡献都是少数是。但是看看样例怎么会有这些神奇的小数。于是大胆猜想是不是与这个数等于多少个，于是就有了的好成绩

#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;
}

• 

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

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

  #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;
  }