URL:
http://www.codechef.com/COOK31/problems/CHEFHCK2
题意：
定义两种数：
1、A^B 形式的（A,B >= 2）
2、非1形式的。
给出一个数x （<= 3141^5）如果是1形式的数求出之前有多少个1形式的数，如果不是1形式的数那么首先倍增2 ， 4 。。。。如果落在 2 ^ (k - 1) - 2 ^ k 区间内那么二分，求次数。
解法：
尼玛这是sb题啊！！要什么解法。。
首先预处理 B>=3 的情况， 一共6e5左右个数字。
然后对于第二种Query，暴力就好了。。
Code：
bool _;
LL n;
vector<LL> h;
const LL limit = 305731144433251701ll;
bool isdouble(LL x){
LL y = sqrt(x);
return y * y == x;
}
void init(){
h.clear();
for (LL i = 3 ; i <= 61 ; i += 2){
double ii = i;
for (LL j = 2 ; ; j ++){
if (isdouble(j)) continue;
double k = pow(1.*j , 1.*i);
if (Geo::dblcmp(k - (double)limit) > 0) break;
LL kk = pow(j , i);
if (kk <= limit){
if (!isdouble(kk))
h.PB(kk);
}
else break;
}
}
UNQ(h);
// REP(i , 50) OT(h[i]);
// cout << h[SZ(h) - 1] << endl;
// OT(SZ(h));
}
VI :: iterator iter;
LL gao(LL x){
LL ret = (LL)sqrt((double)x) - 1;
// OT(ret);
LL p = lower_bound(ALL(h) , x) - h.begin();
ret += p + 1;
// OT(h[p]);
if (h[p] != x) --ret;
return ret;
}
bool check(LL x){
LL p = lower_bound(ALL(h) , x) - h.begin();
if (h[p] == x) return true;
p = sqrt(x);
return (sqr(p) == x);
}
LL A(LL x){
LL low = 0 , high = limit , mid , ret = high;
do{
mid = low + high >> 1;
if (mid + 1 - gao(mid) < x) low = mid + 1;
else{
checkMin(ret , mid);
high = mid - 1;
}
}while(low <= high);
return ret;
}
LL f(LL x){
return lg2(cover_bit(x)) + lg2(high_bit(x)) - lg2(low_bit(x));
//return 2 * lg2(high_bit(x)) - lg2(low_bit(x));
}
LL rev(long long x)
{
if (x == 0) return 1;
// printf("\nLess than %lld : %lld\n" , x , gao(x));
return x - gao(x) + 1;
}
LL solve2(){
LL low = 0 , high = n * 2 , mid , ret = 0 , now = 1;
// do{
// mid = low + high >> 1;
// LL cc = A(mid);
// if (cc == n){
// res = mid;
// break;
// }
// if(cc < n) low = mid + 1;
// else high = mid - 1;
// }while(1);
// LL now = 1 , ret = 0;
LL res = rev(n);
/** Method 1
do{
now <<= 1LL;
ret ++;
}while(now < res);
if (now == res) return ret;
low = now / 2 , high = now;
do{
mid = low + high >> 1;
++ret;
// printf("%lld " , mid);OT(now);
if (mid == res) break;
if (mid < res) low = mid;
else high = mid;
}while(low <= high);
assert(mid == res);
return ret;
*/
return f(res);/** Method 2*/
/**这两个方法是等价的，都是求要二分多少次*/
}
void solve(){
RD(n);
double nn = n;
LL ans;
if (n == 0) ans = 2;
else if (n == 1) ans = 1;
else{
if(check(n)) ans = gao(n);
else {
ans = solve2();
}
}
if (_) printf(" ");
_ = true;
printf("%lld" , ans);
}
int main(){
// freopen("0.in" ,"r" , stdin);
// freopen("output.txt" , "w" , stdout);
_ = false;
init();
Rush solve();
puts("");
}