题目链接：https://vjudge.net/contest/336724#problem/I
题意：给出一个区间L~R，问在里面能找到多少个x满足 L ≤ x ≤ R 且 x = ap （a > 0, p > 1）
思路：找出a的3次幂以上的数，可以缩小为1e6，2次幂的数可以用开根号求，3次幂以上的去个重
#include<bits/stdc++.h> #define ll long long using namespace std; ll n,l,r,tot; ll A[2000000]; const ll mxx=1e18; ll mi(ll x,ll k) { ll ans=1; for(ll i=1;i<=k;i++) { if(ans>mxx/x) return mxx+100; ans*=x; } return ans; } bool is_square(ll x) { ll q=sqrt(x); if(q*q==x) return true; if((q+1)*(q+1)==x) return true; if((q-1)*(q-1)==x) return true; return false; } ll solve(ll x) { ll ans=0; ans+=sqrt(x); ans+=upper_bound(A,A+tot,x)-A; return ans; } int main() { for(ll i=2; i*i*i<=mxx; i++) { for(ll j=3;;j++) { ll v=mi(i,j); if(v>mxx) break; if(is_square(v)) continue; A[tot++]=v; } } sort(A,A+tot); tot=unique(A,A+tot)-A; for(scanf("%lld",&n);n;n--) { scanf("%lld%lld",&l,&r); printf("%lld\n",solve(r)-solve(l-1)); } }
