Educational Codeforces Round 33 (Rated for Div. 2) B题. Beautiful Divisors

B. Beautiful Divisors

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Recently Luba learned about a special kind of numbers that she calls beautiful numbers. The number is called beautiful iff its binary representation consists of k + 1 consecutive ones, and then k consecutive zeroes.

Some examples of beautiful numbers:

• 1₂ (1₁₀);
• 110₂ (6₁₀);
• 1111000₂ (120₁₀);
• 111110000₂ (496₁₀).

More formally, the number is beautiful iff there exists some positive integer k such that the number is equal to (2^k - 1) * (2^k - 1).

Luba has got an integer number n, and she wants to find its greatest beautiful divisor. Help her to find it!

Input

The only line of input contains one number n (1 ≤ n ≤ 10⁵) — the number Luba has got.

Output

Output one number — the greatest beautiful divisor of Luba's number. It is obvious that the answer always exists.

Examples

Input

3

Output

1

Input

992

Output

496

 题意：100000 以内 有几个 美丽的数字 ， 分别是 ：

　　1(2)->1(10)    110(2)->6(10)   11100(2)->28(10)   1111000(2) -> 120(10)   111110000(2)->496(10)   11111100000(2) -> 2016(10)

       1111111000000(2) -> 8128(10)     111111110000000(2) -> 32640(10)    11111111100000000(2) -> 130816(10)

        注意看题 ， 题目要的是  ：“满足 是 n 的 除数 同时 是美丽数字 两个条件的最大数字” ，

/*  预处理  */ 
#include<stdio.h>
#include<string.h>
#include <iostream>
#include<algorithm>

using namespace std;
#define maxn 200
int num[maxn] ; 

void init(){
    num[1] = 1 ; 
    num[2] = 6 ; 
    num[3] = 28 ; 
    num[4] = 120 ; 
    num[5] = 496 ;
    num[6] = 2016 ; 
    num[7] = 8128 ; 
    num[8] = 32640 ; 
    num[9] = 130816 ; 
    
}

int main(){
    int n ; 
    init() ; 
    
    while(~scanf("%d" , &n)){
        for(int i=9 ; i>0 ; i--){
            if(num[i]<=n&&(n%num[i] == 0 )){
                printf("%d
" , num[i]) ; 
                break ; 
            }
        }
    }
    
    return 0 ; 
}

/* 快速幂判断美丽数字  */ 
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std ;

#define LL long long
// 快速幂  
LL pow_x(int k ) {
    LL result = 1 ;
    LL a = 2 ;

    while(k) {
        if(k&1) {
            result = result * a ;
        }
        a = a*a ;
        k=k/2 ;
    }
    return result ;
}

int main() {

    int n ;
    while(~scanf("%d" , &n)) {
        bool flag = false ;
        int result ;
        for(int i=n ; i>0 ; i--) {
            for(int k = 1 ; ; k++ ) {
                if((pow_x(k)-1)*pow_x(k-1) == i ) {
                    if(n%i==0) {
                        result = i ;
                        flag = true ;
                        break ;
                    }

                }
                
                if((pow_x(k)-1)*pow_x(k-1) > i ) {
                    break ;
                }
            }
            if(flag) {
                break;
            }
        }
        printf("%d
" , result) ;
    }
    return 0 ;

}