848      技術社區[雲棲]

cc End Of The World 2

      題解上寫easy的一道題，但是也沒寫出來。題目很好，考察的非常靈活。

     我覺得再好的題解也沒有官方的優秀，所以就直接上傳送門：https://discuss.codechef.com/questions/6650/chefhck2-editorial

      中間有些小細節可以優化。但算法我覺得基本上已經很完美了。

     標程裏也有很多小亮點：

      1.x&-x是求可以整除x的最大2的冪。

      2,若k在[2^b-1,2^b]間，並且k=2^k*m，則二分共要b-k次

/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
int n;
long long Max=305731144433251701LL;
inline int sqr(long long a)
{
    int x=sqrt(a);
    return x;
}
inline bool issqr(long long a)
{
    int x=sqr(a);
    if((long long)x*x==a)return 1;
    else return 0;
}
vector<long long> pws;
void pre()
{
    long long i;
    vector<long long> pw3,pw5;
    pw3.reserve(700000);
    pw5.reserve(30000);
    long long t,a,b;
    bool f=0;
    for(i=2;;i++)
    {
        if(issqr(i))continue;
        a=(long long)i*i;
        b=a*i;
        if(b>Max)break;
        pw3.push_back(b);
        if(f)continue;
        if(i>=3141)f=1;
        t=Max/a;
        b*=a;
        while(b<=t)
        {
            pw5.push_back(b);
            b*=a;
        }
        if(b<=Max)pw5.push_back(b);
    }
    sort(pw5.begin(),pw5.end());
    pws.resize(pw3.size()+pw5.size());
    merge(pw3.begin(),pw3.end(),pw5.begin(),pw5.end(),pws.begin())-pws.begin();
    pws.erase(unique(pws.begin(),pws.end()),pws.end());
}
inline int l2(long long a)
{
    return ceil(log2(a));
}
int bin_search(long long x)
{
    long long t=x&-x;
    if(t==x)  return l2(x);
    return 2*l2(x)-l2(t)-1;
}
int solve(long long x)
{
    if(x<=1)return 2-x;
    int y=sqr(x);
    int is_sqr=issqr(x);
    int j=(lower_bound(pws.begin(),pws.end(),x)-pws.begin());
    if(is_sqr||pws[j]==x) return j-is_sqr+y;
    else return bin_search(x+1-j-(y-1));
}
int main()
{
    pre();
    int T;
    long long x;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%lld",&x);
        printf("%d%c",solve(x),T?' ':'\n');
    }
}

最後更新：2017-04-04 07:03:49

  上一篇： 各大計算機公司 筆試及麵試 題目 - 騰訊

  下一篇： Android多媒體學習：檢索MediaStore中的Video和其對應的縮略圖信息