C3. Dawn of the planet of the Rastas

Codeforces

IDCFC3

Time15000ms

Memory1024MB

Difficulty—

English · Original

Chinese · Translation

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]

由于 Mike 的暴行，Rastas 攻击了他的国家（当然为了帮助他的人民），并正向首都推进。 Rastas 的军队有 #cf_span[2n - 1] 名士兵，编号为 #cf_span[i] 的士兵的战斗力等于数字 #cf_span[i] 的二进制表示中 1 的个数（士兵编号从 #cf_span[1] 到 #cf_span[2n - 1]）。如果数字 #cf_span[a] 和 #cf_span[b] 的最大公约数为 #cf_span[gcd(a, b)]，则我们知道这支军队的战斗力 #cf_span[S] 等于：作为 Mike 的大臣，你的职责是计算 #cf_span[S] 对 #cf_span[109 + 7] 取模的结果。子任务：每个子任务包含一个测试用例。输入包含一个整数 #cf_span[n]。请在一行中输出答案对 #cf_span[109 + 7] 取模的结果。 ## Input 每个子任务包含一个测试用例。输入包含一个整数 #cf_span[n]。 ## Output 请在一行中输出答案对 #cf_span[109 + 7] 取模的结果。 [samples]

Let $ n $ be a positive integer. Define the set of soldiers indexed from $ 1 $ to $ 2^n - 1 $. For each soldier $ i $, define its strength as $ s(i) = \text{popcount}(i) $, the number of 1-bits in the binary representation of $ i $. The army strength $ S $ is defined as: $$ S = \sum_{a=1}^{2^n - 1} \sum_{b=1}^{2^n - 1} \gcd(s(a), s(b)) $$ Compute $ S \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": "CFC3"
  },
  "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": "由于 Mike 的暴行，Rastas 攻击了他的国家（当然为了帮助他的人民），并正向首都推进。\n\nRastas 的军队有 #cf_span[2n - 1] 名士兵，编号为 #cf_span[i] 的士兵的战斗力等于数字 #cf_span[i] 的二进制表示中 1 的个数（士兵编号从 #cf_span[1] 到 #cf_span[2n - 1]）。\n\n如果数字 #cf_span[a] 和 #cf_s...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Let $ n $ be a positive integer. Define the set of soldiers indexed from $ 1 $ to $ 2^n - 1 $. For each soldier $ i $, define its strength as $ s(i) = \\text{popcount}(i) $, the number of 1-bits in the...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments