B. Taxes

Codeforces

IDCF736B

Time2000ms

Memory256MB

Difficulty—

mathnumber theory

English · Original

Chinese · Translation

Formal · Original

Mr. Funt now lives in a country with a very specific tax laws. The total income of mr. Funt during this year is equal to _n_ (_n_ ≥ 2) burles and the amount of tax he has to pay is calculated as the maximum divisor of _n_ (not equal to _n_, of course). For example, if _n_ = 6 then Funt has to pay 3 burles, while for _n_ = 25 he needs to pay 5 and if _n_ = 2 he pays only 1 burle. As mr. Funt is a very opportunistic person he wants to cheat a bit. In particular, he wants to split the initial _n_ in several parts _n_1 + _n_2 + ... + _n__k_ = _n_ (here _k_ is arbitrary, even _k_ = 1 is allowed) and pay the taxes for each part separately. He can't make some part equal to 1 because it will reveal him. So, the condition _n__i_ ≥ 2 should hold for all _i_ from 1 to _k_. Ostap Bender wonders, how many money Funt has to pay (i.e. minimal) if he chooses and optimal way to split _n_ in parts. ## Input The first line of the input contains a single integer _n_ (2 ≤ _n_ ≤ 2·109) — the total year income of mr. Funt. ## Output Print one integer — minimum possible number of burles that mr. Funt has to pay as a tax. [samples]

Mr. Funt 现在生活在一个税收法律非常特殊的国家。Mr. Funt 今年的总收入为 $n$（$n ≥ 2$）布尔，他需要缴纳的税款为 $n$ 的最大真因子（即不超过 $n$ 且不等于 $n$ 的最大因子）。例如，若 $n = 6$，则 Funt 需支付 $3$ 布尔；若 $n = 25$，则需支付 $5$ 布尔；若 $n = 2$，则只需支付 $1$ 布尔。由于 Mr. Funt 是一个非常善于投机的人，他想稍微作弊一下。具体来说，他想将初始的 $n$ 拆分成若干部分 $n_1 + n_2 + ... + n_k = n$（这里 $k$ 可以是任意正整数，甚至允许 $k = 1$），并对每一部分分别缴税。他不能让任何一部分等于 $1$，因为那样会暴露他。因此，对所有 $i$ 从 $1$ 到 $k$，必须满足 $n_i ≥ 2$。 Ostap Bender 想知道，如果 Funt 选择最优的拆分方式，他最少需要支付多少税款。输入的第一行包含一个整数 $n$（$2 ≤ n ≤ 2·10^9$）— Mr. Funt 的年总收入。请输出一个整数 — Mr. Funt 最少需要支付的税款（以布尔为单位）。 ## Input 输入的第一行包含一个整数 $n$（$2 ≤ n ≤ 2·10^9$）— Mr. Funt 的年总收入。 ## Output 请输出一个整数 — Mr. Funt 最少需要支付的税款（以布尔为单位）。 [samples]

**Definitions** Let $ n \in \mathbb{Z} $, $ n \geq 2 $, be the total income. For any integer $ m \geq 2 $, define $ T(m) $ as the largest proper divisor of $ m $, i.e., $ T(m) = \max\{ d \mid d \mid m, 1 \leq d < m \} $. **Constraints** 1. $ 2 \leq n \leq 2 \cdot 10^9 $ 2. A partition of $ n $ is a tuple $ (n_1, n_2, \dots, n_k) $ with $ k \geq 1 $, $ n_i \geq 2 $ for all $ i $, and $ \sum_{i=1}^k n_i = n $. **Objective** Minimize the total tax: $$ \min_{\substack{(n_1,\dots,n_k) \\ \sum n_i = n \\ n_i \geq 2}} \sum_{i=1}^k T(n_i) $$

Samples

Input #1

Output #1

Input #2

Output #2

API Response (JSON)

{
  "problem": {
    "name": "B. Taxes",
    "description": {
      "content": "Mr. Funt now lives in a country with a very specific tax laws. The total income of mr. Funt during this year is equal to _n_ (_n_ ≥ 2) burles and the amount of tax he has to pay is calculated as the m",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF736B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Mr. Funt now lives in a country with a very specific tax laws. The total income of mr. Funt during this year is equal to _n_ (_n_ ≥ 2) burles and the amount of tax he has to pay is calculated as the m...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Mr. Funt 现在生活在一个税收法律非常特殊的国家。Mr. Funt 今年的总收入为 $n$（$n ≥ 2$）布尔，他需要缴纳的税款为 $n$ 的最大真因子（即不超过 $n$ 且不等于 $n$ 的最大因子）。例如，若 $n = 6$，则 Funt 需支付 $3$ 布尔；若 $n = 25$，则需支付 $5$ 布尔；若 $n = 2$，则只需支付 $1$ 布尔。\n\n由于 Mr. Funt 是一个...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $, $ n \\geq 2 $, be the total income.  \nFor any integer $ m \\geq 2 $, define $ T(m) $ as the largest proper divisor of $ m $, i.e., $ T(m) = \\max\\{ d \\mid d \\m...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments