C3. Dawn of the planet of the Rastas

Codeforces

IDCF10070C3

Time15000ms

Memory1024MB

Difficulty—

English · Original

Formal · Original

Due to the cruelties of Mike, Rastas attacked his country (to help its people of course) and they're moving forward to the capital. Rastas' army has 2n - 1 soldiers and the strength of soldier number i is the number of set bits (bits equal to 1) in binary representation of number i (soldiers are numbered from 1 to 2n - 1). If the greatest common divisor of numbers a and b is gcd(a, b), we know that strength of this army which we show with S is equal to: As the minister of Mike, it's your duty to calculate S modulo 109 + 7. Subtasks: Each subtask consists of one testcase. Input consists of one integer, n. Print the answer modulo 109 + 7 in a single line. ## Input Each subtask consists of one testcase.Input consists of one integer, n. ## Output Print the answer modulo 109 + 7 in a single line. [samples]

**Definitions** Let $ n \in \mathbb{Z}^+ $. Let $ m = 2^n - 1 $. For each $ i \in \{1, 2, \dots, m\} $, define the strength of soldier $ i $ as $ s(i) = \text{popcount}(i) $, the number of 1-bits in the binary representation of $ i $. **Given** For all $ a, b \in \{1, 2, \dots, m\} $, it holds that $ \gcd(a, b) = \gcd(s(a), s(b)) $. **Objective** Compute: $$ S = \sum_{a=1}^{m} \sum_{b=1}^{m} \gcd(s(a), s(b)) \mod (10^9 + 7) $$

API Response (JSON)

{
  "problem": {
    "name": "C3. Dawn of the planet of the Rastas",
    "description": {
      "content": "Due to the cruelties of Mike, Rastas attacked his country (to help its people of course) and they're moving forward to the capital.  Rastas' army has 2n - 1 soldiers and the strength of soldier numbe",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 15000,
      "memory_limit": 1048576
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10070C3"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Due to the cruelties of Mike, Rastas attacked his country (to help its people of course) and they're moving forward to the capital. \n\nRastas' army has 2n - 1 soldiers and the strength of soldier numbe...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $.  \nLet $ m = 2^n - 1 $.  \nFor each $ i \\in \\{1, 2, \\dots, m\\} $, define the strength of soldier $ i $ as $ s(i) = \\text{popcount}(i) $, the number of 1-bit...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments