C. Constant Ratio

Codeforces

IDCF10091C

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Given an integer n, find out number of ways to represent it as the sum of two or more integers ai with the next property: ratio ai / ai - 1 is the same positive integer for all possible i > 1. Input consists of one integer n (1 ≤ n ≤ 105). Print one integer — number of representations. In the first sample no such representation exists. In the second sample there exist two representations: ## Input Input consists of one integer n (1 ≤ n ≤ 105). ## Output Print one integer — number of representations. [samples] ## Note In the first sample no such representation exists.In the second sample there exist two representations: 1 1 1 1 1, then q = 1. 1 4, then q = 4.

**Definitions** Let $ n \in \mathbb{Z} $ with $ 1 \leq n \leq 10^5 $. A representation of $ n $ is a sequence of integers $ (a_1, a_2, \dots, a_k) $ with $ k \geq 2 $, such that: - $ \sum_{i=1}^k a_i = n $, - $ a_i \in \mathbb{Z}^+ $ for all $ i $, - $ \frac{a_i}{a_{i-1}} = r $ for all $ i \in \{2, \dots, k\} $, where $ r \in \mathbb{Z}^+ $ is a constant ratio. **Objective** Count the number of such sequences $ (a_1, a_2, \dots, a_k) $ satisfying the above conditions.

API Response (JSON)

{
  "problem": {
    "name": "C. Constant Ratio",
    "description": {
      "content": "Given an integer n, find out number of ways to represent it as the sum of two or more integers ai with the next property: ratio ai / ai - 1 is the same positive integer for all possible i > 1. Input ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10091C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Given an integer n, find out number of ways to represent it as the sum of two or more integers ai with the next property: ratio ai / ai - 1 is the same positive integer for all possible i > 1.\n\nInput ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ with $ 1 \\leq n \\leq 10^5 $.  \nA representation of $ n $ is a sequence of integers $ (a_1, a_2, \\dots, a_k) $ with $ k \\geq 2 $, such that:  \n- $ \\sum_{i=1}^...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments