You're given Q queries of the form (L, R).
For each query you have to find the number of such x that L ≤ x ≤ R and there exist integer numbers a > 0, p > 1 such that x = ap.
Input
The first line contains the number of queries Q (1 ≤ Q ≤ 105).
The next Q lines contains two integers L, R each (1 ≤ L ≤ R ≤ 1018).
Output
Output Q lines — the answers to the queries.
Example
Input
6 1 4 9 9 5 7 12 29 137 591 1 1000000Output
2 1 0 3 17 1111Note
In query one the suitable numbers are 1 and 4.
给定一个区间[l,r]，问区间内有多少个数x满足x=a^q，并且a>0&&q>1
问存在多少个x满足x=a^q，如果数据小的话可以直接把a^q出现的数字用map容器存储起来，排个序输出就行了。
不过，这道题的l和r的范围是1e19，没办法对所有范围的数据都暴力存储起来，不过我们可以对部分进行这样的操作。
当q=2的时候，a的范围是1e9，单独分析：
毋庸置疑，x^2在x轴上是单调的，那么我们就可以使用二分的方法判断在[l,r]区间范围内有多少个x^2。
右边界：r，左边界：l-1
通过右边界对应的数我们找到一个x，通过左边界对应的数我们找到一个数y，那么x-y就是指数为2的数量。
当q>2的时候，a的范围小于等于1e6，可以暴力：
将所有的情况使用map容器存起来，然后用sort进行一个排序，接下来使用upper_bound函数找到l和r中间有多少个数成立。
代码如下：
#include<cstdio> #include<iostream> #include<algorithm> #include<string> #include<string.h> #include<vector> #include<map> using namespace std; typedef long long ll; vector<ll>number; map<ll,int>mapp; bool sqrtt(ll x) { ll y=sqrt(x); if(y*y==x||(y+1)*(y+1)==x||(y-1)*(y-1)==x) return true; return false; } void init() { number.push_back(1); for(ll i=2;i<=1e6;++i) { for(ll j=i*i*i;j<=1e18;j*=i) { if(!mapp[j]&&!sqrtt(j)) { //去重复的数字和平方数字 mapp[j]=1; number.push_back(j); } if(1e18/i<j) break; } } sort(number.begin(),number.end()); } ll value(ll x) { ll l=1,r=1e9; ll mid,ans=0; while(l<=r) { mid=(l+r)/2; if(mid*mid<=x) { ans=mid; l=mid+1; } else r=mid-1; } return ans; } ll solve(ll l,ll r) { return value(r)-value(l-1); } int main() { ll T,l,r; init(); cin>>T; while(T--) { scanf("%I64d%I64d",&l,&r); ll ans=0; ans+=upper_bound(number.begin(),number.end(),r)-upper_bound(number.begin(),number.end(),l-1); ans+=solve(l,r); if(l==1) ans-=1; printf("%I64d\n",ans); } return 0; }
