记录编号	99907	评测结果	AAAAAAAAAAAAAAAAA
题目名称	[Ural 1396] 最大值2	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.540 s
提交时间	2014-05-01 21:29:42	内存使用	0.31 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
using namespace std;
typedef unsigned long long ll;
typedef pair<ll,ll> PL;
PL F[100];//以A,B为前两项(下标从0开始)的广义Fibonacci数列,第i项可用A,B线性表示
ll gen_Fib(ll n,ll a,ll b){
	return F[n].first*a+F[n].second*b;
}
ll N;
ll Solve(ll cnt,ll left,ll right,ll lv,ll rv){//cnt代表这一段中的最大值从(lv,rv)开始走了cnt步
	ll mid=(left+right)>>1;
	ll mv=(lv+rv);
	ll ans=0;
	if(mid<=N){
		ans=gen_Fib(cnt-1,lv,mv);
		if(mid<N){
			ans=max(ans,Solve(cnt-1,mid,right,mv,rv));
		}
		return ans;
	}
	else return Solve(cnt-1,left,mid,lv,mv);
}
void init(void){
	F[0]=make_pair(1,0);
	F[1]=make_pair(0,1);
	for(int i=2;i<=65;i++){
		F[i].first=F[i-1].first+F[i-2].first;
		F[i].second=F[i-1].second+F[i-2].second;
	}
}
bool read(void){
	cin>>N;
	return N!=0;
}
ll bitnum(ll n){
	ll ans=0;
	while(n){
		ans++;
		n>>=1;
	}
	return ans;
}
ll pow2(ll n){
	ll ans=1;
	while(n--) ans*=2;
	return ans;
}
void work(void){
	ll T=bitnum(N);
	ll ans=gen_Fib(T-1,1,1);
	ans=max(ans,Solve(T,pow2(T-1),pow2(T),1,1));
	cout<<ans<<endl;
}
int main(){
	freopen("Maximum.in","r",stdin);
	freopen("Maximum.out","w",stdout);
	init();
	while(read()) work();
	return 0;
}