GYM

GYM

Twisting the Number

Professor Dull invented a direction in number theory. This is the theory of “twisting generators”. Considera positive integer number p. Let it contain b bits (the highest bit should be 1). Consider all possible bcycle shifts of the binary notation of the number p. Let’s make a set from all this shifts and call it W(p).Note, some of the shifts can start with zero. Let’s say that the number p twistingly generates the setW(p). For example, W(11) = {7, 11, 13, 14}.The number p is called a twisting generator of the number n, if the union of all sets W(1), W(2), . . . , W(p)contains {1, 2, . . . , n} as a subset. Your task is to find the minimum generator of the given number n.

Input

The first line of the input contains the integer number n (1 ≤ n ≤ 1018).

Output

Write to the output the minimum twisting generator of the number n.

Example

stdin stdout

6  5

题意：给你一个N，问你找到最大的P使得1~P所有数的二进制循环形成的数包括1~N。

解题思路：枚举即可。然后二进制的运算要注意。首先先求得N的二进制循环中，最小的那个数，记为ANS，那么答案肯定在ANS~N之间。即ANS通过循环，能形成N（注意最高位保持为1）然后枚举的时候我们枚举二进制的1就可以了。不要枚举每一个数。

#include<iostream>
#include<bitset>
using namespace std;
typedef long long int ll;
const ll INF=(1LL<<62);//获得最高位的1是第几位
int getHigh(ll x){for(int i=62;i>=0;i--){if(x&(1LL<<i))return i;}
}//通过二进制循环，能获得当前数的最小的那个数
ll get(ll n){ll minn=n;ll temp=n;int hb=getHigh(temp);do{bool h=((1LL<<hb)&temp);temp=temp&((1LL<<hb)-1);temp<<=1;temp|=h;bool hh=((1LL<<hb)&temp);if(temp<minn&&(hh))minn=temp;}while(n!=temp);return minn;
}int main(){ll n;ll ans;cin>>n;ans=get(n);//初始化答案，此时正确的答案肯定在ans~n之间int pos=0;//循环枚举比n小的某些数，如1001001000，我们只用枚举1001000111，1000111111即可，因为除了这些数以外的所有数，肯定能由比ans小的数循环得到。while(n){ll temp=get((n<<pos)-1);if(ans<temp)ans=temp;n>>=1;pos++;}cout<<ans<<endl;return 0;
}