阅读848 返回首页    go 阿里云 go 技术社区[云栖]

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

  上一篇：go 各大计算机公司 笔试及面试 题目 - 腾讯
  下一篇：go Android多媒体学习：检索MediaStore中的Video和其对应的缩略图信息