SGU178 解题手记
　　为了让拆的次数最少，必须让每一段尽可能的大。每拆一次，就会得到一段长度为1的，以及被拆的link左边和右边的两段。假设需要拆x次，那么就会得到x段长度为1的，其他的段就应该排成(x+1),(x+1)*2,(x+1)*4,(x+1)*8,...
　　其实就是求一个不等式：
　　x+(x+1)+(x+1)*2+...+(x+1)*2^x>=N
　　(x+1)*2^(x+1)>=N+1
　　的最小整数解，即解(x+1)*2^(x+1)=N+1后向上取整。
　　由于x+1>=1，所以2^(x+1)<=log(N+1)。而(x+1)*2^(x+1)具有单调性，所以可以在[0,log(N+1)]中二分找解。
　　由于N小于10^16，所以log(N+1)不超过54，这给了我们一个打表的机会，事实上，x的最大值是47。
　　Submit 1: AC。虽然是很无赖的代码。

?View Code CPP
1
2
3
4
5
6
7
8
9
10
11
12

#include <iostream>
using namespace std;
 
const long long ns[48]={1LL,7LL,23LL,63LL,159LL,383LL,895LL,2047LL,4607LL,10239LL,22527LL,49151LL,106495LL,229375LL,491519LL,1048575LL,2228223LL,4718591LL,9961471LL,20971519LL,44040191LL,92274687LL,192937983LL,402653183LL,838860799LL,1744830463LL,3623878655LL,7516192767LL,15569256447LL,32212254719LL,66571993087LL,137438953471LL,283467841535LL,584115552255LL,1202590842879LL,2473901162495LL,5085241278463LL,10445360463871LL,21440476741631LL,43980465111039LL,90159953477631LL,184717953466367LL,378231999954943LL,774056185954303LL,1583296743997439LL,3236962232172543LL,6614661952700415LL,13510798882111487LL};
 
int main()
{
    long long N;
    cin>>N;
    cout<<(upper_bound(ns,ns+48,N)-ns-binary_search(ns,ns+48,N))<<endl;
    return 0;
}