\(x=1\) としたとき、 \(a=1\) とすると任意の \(2\) 以上の整数 \(b\) について \(x=a^b\) が成り立つため、 \(1\) は問題文中の条件を満たします。
この特殊な事例は取り扱いづらいので、以降は \(2\) 以上の整数であって条件を満たすものがいくつあるかを考えます。

まず、もし整数 \(x\) が \(a^b\) と表現されるなら、それがどのように表現されうるかを明らかにしましょう。

例として、整数 \(x=64=2^6\) を考えます。

• \(x\) は \(a=2^3\) とすることで、 \(a^2\) の形で表現できます。
• \(x\) は \(a=2^2\) とすることで、 \(a^3\) の形で表現できます。
• \(x\) は \(a=2^1\) とすることで、 \(a^6\) の形で表現できます。

もうひとつ、整数 \(x=2985984 = 2^{12} \times 3^6\) を考えます。

• \(x\) は \(a=(2^6 \times 3^3)\) とすることで、 \(a^2\) の形で表現できる。
• \(x\) は \(a=(2^4 \times 3^2)\) とすることで、 \(a^3\) の形で表現できる。
• \(x\) は \(a=(2^2 \times 3^1)\) とすることで、 \(a^6\) の形で表現できる。

より一般に、 \(x\) の素因数分解を \(x=p^lq^mr^n \dots\) としましょう。

• \(l,m,n,\dots\) に共通する約数 \(k\) をひとつ取ったとき、 \(a=p^{(l/k)}q^{(m/k)}r^{(n/k)} \dots\) とすることで、 \(a^k\) の形で表現できる。

このことから、 \(g = \gcd(l,m,n,\dots)\) としたとき、 \(b\) を \(g\) の \(2\) 以上の約数としたとき、またその時に限って題意を満たす \(x=a^b\) の形での表現の方法が存在することが分かります。

次に、 \(b\) を決め打った時に \(a\) としてありうる整数がいくつあるかを求めます。
具体的には \(a^b \le N\) を満たす最大の \(a\) を、全ての \(b\) について求めればよいです。
\(2^{60} > 10^{18}\) なので、この問題の制約下で \(2 \le b < 60\) の範囲を考えれば十分です。
このもとで、各 \(b\) について \(a\) を二分探索すればよいです。
注意として、 \(a^b\) を求める際にオーバーフローしてしまう可能性があります。
この問題を回避するには、例えば \(b\) が小さいことを利用して \(a^b\) を求める際に愚直に \(b\) 回ループを回して \(b\) 乗を試みながら、一度 \(a\) を掛けるごとに先に double 型等で値の大きさを見積もって十分大きくなったら打ち切るというような実装をすればよいです。

\(a^b\) の形で表現できる整数の個数が \(b=2,3,\dots,59\) の全てで出揃ったところで、これらを漏れなく重複なく足し合わせましょう。

約数系包除原理 を使って足し合わせます。
ある整数 \(x\) の素因数分解を \(x=p^lq^mr^n \dots\) とすると、 \(b\) を \(g=\gcd(l,m,n,\dots)\) の \(2\) 以上の約数としたとき、またその時に限って題意を満たす \(x=a^b\) の形での表現の方法が存在することは先ほど示しました。
ここで、 \(g\) の素因数分解を \(P^LQ^MR^N \dots \) とします。以下のようにすると、 \(x\) をちょうど一度だけ数えることができます。

• \(b=P, Q, R, \dots\) ( \(b\) が \(g\) の素因数 \(1\) つの積である ) の場合を足す。
• \(b=PQ, PR, \dots, QR, \dots\) ( \(b\) が \(g\) の素因数 \(2\) つの積である ) の場合を引く。
• \(b=PQR, \dots\) ( \(b\) が \(g\) の素因数 \(3\) つの積である ) の場合を足す。
• \(\vdots\)

このことの証明は通常の包除原理と同様に行うことができます。

よって、結局以下のようにすると条件を満たす整数の数を漏れなく重複なく求めることができます。

• \(b\) に平方因子が含まれる ( \(b\) が同じ素因数を複数含む ) 場合、無視する。
• そうでなく \(b\) に素因数が奇数個含まれる場合、足す。
• そうでなく \(b\) に素因数が偶数個含まれる場合、引く。

以上を実装することで、この問題に \(O(\log^3 N)\) といった時間計算量で正解できます。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

vector<long long> pfact(long long x){
  vector<long long> res;
  for(long long i=2;i*i<=x;i++){
    while(x%i==0){
      res.push_back(i);
      x/=i;
    }
  }
  if(x>1){res.push_back(x);}
  return res;
}

long long safe_pow(long long a,long long b){
  long long res=1;
  for(long long i=0;i<b;i++){
    double dres=res;
    dres*=a;
    if(dres>2e18){return 2e18;}
    res*=a;
  }
  return res;
}

int main(){
  long long n;
  cin >> n;
  long long res=0;
  for(long long b=2;b<60;b++){
    long long l=2,r=2e9;
    while(l<=r){
      long long t=(l+r)/2;
      if(safe_pow(t,b)>n){r=t-1;}
      else{l=t+1;}
    }
    // a = [2,r] satisfy a^b <= n
    vector<long long> pf=pfact(b);
    bool same=false;
    for(long long i=1;i<pf.size();i++){
      if(pf[i-1]==pf[i]){same=true; break;}
    }
    if(same){continue;}
    if(pf.size()%2){res+=(r-1);}
    else{res-=(r-1);}
  }
  res++; // count 1
  cout << res << "\n";
  return 0;
}