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:

  • 12 (110);
  • 1102 (610);
  • 11110002 (12010);
  • 1111100002 (49610).

More formally, the number is beautiful iff there exists some positive integer k such that the number is equal to (2k - 1) * (2k - 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 ≤ 105) — 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

【题意】:beautiful数定义:如果该数在二进制下表示由k+1个连续的1个,接着k个连续的0组成,则该数字称为beautiful的。比如:

Educational Codeforces Round 33 (Rated for Div. 2) B. Beautiful Divisors【进制思维/打表】

换句话说,当且仅当存在一些正整数k使得这个 number =  ( 2k - 1 ) * ( 2^(k - 1) ) ,这个number就是beautiful的。现在给你一个number,求它最大beautiful因子。

【分析】:打表得到K为最大9。求最大因子数可以逆向枚举。

【代码】:beautiful numbers表:

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 ; }
#include <bits/stdc++.h>

using namespace std;
const int N = ;
int n;
int a[N];
int main()
{
for(int i=;i<=;i++) a[i]=(pow(,i)-)*pow(,i-);
scanf("%d",&n);
for(int i=;i>=;i--) if(n%a[i]==) {printf("%d\n",a[i]);break;}
return ;
}
上一篇:生成pgsql表结构的程序


下一篇:ORACLE MERGE INTO语句,unable to get a stable set of rows in the source tables报错解决