Yellowstar likes integers so much that he listed all positive integers in ascending order,but he hates those numbers which can be written as a^b (a, b are positive integers,2<=b<=r),so he removed them all.Yellowstar calls the sequence that formed by the rest integers“Y sequence”.When r=3,The first few items of it are：
2,3,5,6,7,10......
Given positive integers n and r，you should output Y(n)(the n-th number of Y sequence.It is obvious that Y(1)=2 whatever r is).
2,3,5,6,7,10......
Given positive integers n and r，you should output Y(n)(the n-th number of Y sequence.It is obvious that Y(1)=2 whatever r is).
InputThe first line of the input contains a single number T:the number of test cases.
Then T cases follow, each contains two positive integer n and r described above.
n<=2*10^18,2<=r<=62,T<=30000.
OutputFor each case,output Y(n).Sample Input
2
10 2
10 3
Sample Output
13
14
题意：F(x)表示不大于x的而且满足不少a^b形式的个数，求ans，使得F(ans)=N。
思路：我们可以荣容斥的方法求F(x)。 所以可以用二分来得到答案，但是我们可以用二分超时。 所以我们需要用高效的方法。
先假设当前答案是ans，然后求F(ans)，如果F(ans)<N，表示还至少缺N-F(ans)个，所以ans=ans+N-F(ans)，继续下一次验证，直到F(ans)==N。
这样优于二分的原因是a^b的形式比较离散，所以迭代的次数比较少。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int prime[]={-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-};
vector<int>p;
void getR(int R)
{
p.clear();
for(int i=;abs(prime[i])<=R;i++){
int sz=p.size();
for(int j=;j<sz;j++){
if(abs(prime[i]*p[j])<=)p.push_back(prime[i]*p[j]);
}
p.push_back(prime[i]);
}
}
ll cal(ll x)
{
if(x==) return ;
ll res=x;
for(int i=;i<p.size();i++){
ll tmp=(ll)pow(x+0.5,1.0/abs(p[i]))-;
if(p[i]<) res-=tmp;
else res+=tmp;
}
return res-;
}
void solve(ll N,int R)
{
getR(R); ll ans=N;
while(){
ll tmp=cal(ans);
if(tmp==N) break;
ans+=N-tmp;
}
printf("%I64d\n",ans);
}
int main()
{
int T,R; ll N;
scanf("%d",&T);
while(T--){
scanf("%I64d%d",&N,&R);
solve(N,R);
}
return ;
}
超时的二分代码：
#include<bits/stdc++.h>
#define ll unsigned long long
using namespace std;
int prime[]={-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-};
vector<int>p;
void getR(int R)
{
p.clear();
for(int i=;abs(prime[i])<=R;i++){
int sz=p.size();
for(int j=;j<sz;j++){
if(abs(prime[i]*p[j])<=)p.push_back(prime[i]*p[j]);
}
p.push_back(prime[i]);
}
}
ll cal(ll x)
{
if(x==) return ;
ll res=x;
for(int i=;i<p.size();i++){
ll tmp=(ll)pow(x+0.5,1.0/abs(p[i]))-;
if(p[i]<) res-=tmp;
else res+=tmp;
}
return res-;
}
void solve(ll N,int RR)
{
getR(RR); ll L=N,R=L+,ans;
while(L<=R){
ll Mid=(L+R)/;
if(cal(Mid)>=N) ans=Mid,R=Mid-;
else L=Mid+;
}
cout<<ans<<endl;
}
int main()
{
int T,R; ll N;
scanf("%d",&T);
while(T--){
cin>>N>>R;
solve(N,R);
}
return ;
}