B. Beautiful Divisors

Codeforces
IDCF893B
Time2000ms
Memory256MB
Difficulty
brute forceimplementation
English · Original
Chinese · Translation
Formal · Original
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 (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_ ≤ 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. [samples]
最近,Luba 学习了一种她称为 _beautiful_ 数的特殊数字。一个数字被称为 _beautiful_,当且仅当它的二进制表示由 #cf_span[k + 1] 个连续的 1,后跟 #cf_span[k] 个连续的 0 组成。 一些 beautiful 数的例子: 更形式化地说,一个数字是 beautiful 的,当且仅当存在某个正整数 #cf_span[k],使得该数字等于 #cf_span[(2k - 1) * (2k - 1)]。 Luba 得到了一个整数 #cf_span[n],她希望找到它的最大的 beautiful 因子。请帮助她找到它! 输入仅包含一行,包含一个数字 #cf_span[n](#cf_span[1 ≤ n ≤ 105])——Luba 得到的数字。 输出一个数字——Luba 的数字的最大 beautiful 因子。显然答案总是存在的。 ## Input 输入仅包含一行,包含一个数字 #cf_span[n](#cf_span[1 ≤ n ≤ 105])——Luba 得到的数字。 ## Output 输出一个数字——Luba 的数字的最大 beautiful 因子。显然答案总是存在的。 [samples]
**Definitions** Let $ k \in \mathbb{Z}^+ $. A number $ b_k $ is *beautiful* if: $$ b_k = (2^k - 1) \cdot 2^{k-1} $$ **Given** An integer $ n \in \mathbb{Z} $ such that $ 1 \leq n \leq 10^5 $. **Objective** Find the greatest divisor $ d $ of $ n $ such that $ d = b_k $ for some $ k \in \mathbb{Z}^+ $.
Samples
Input #1
3
Output #1
1
Input #2
992
Output #2
496
API Response (JSON)
{
  "problem": {
    "name": "B. Beautiful Divisors",
    "description": {
      "content": "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 ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF893B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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 ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "最近,Luba 学习了一种她称为 _beautiful_ 数的特殊数字。一个数字被称为 _beautiful_,当且仅当它的二进制表示由 #cf_span[k + 1] 个连续的 1,后跟 #cf_span[k] 个连续的 0 组成。\n\n一些 beautiful 数的例子:\n\n更形式化地说,一个数字是 beautiful 的,当且仅当存在某个正整数 #cf_span[k],使得该数字等于 #cf_...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ k \\in \\mathbb{Z}^+ $. A number $ b_k $ is *beautiful* if:  \n$$\nb_k = (2^k - 1) \\cdot 2^{k-1}\n$$\n\n**Given**  \nAn integer $ n \\in \\mathbb{Z} $ such that $ 1 \\leq n \\leq 10^5 $.\n\n...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}
Full JSON Raw Segments