[NERC 2018] Fractions

Luogu

IDLGP9796

Time1750ms

Memory512MB

DifficultyP5

2018Special JudgeICPCNERC/NEERC

给你一个整数 $n$，你需要构造出若干个形如 $\dfrac{a_i}{b_i}$ 的真分数，使得 $\sum^k_{i=1} \frac{a_i}{b_i} = 1 - \frac{1}{n}$，且 $b_i$ 可以整除 $n$。 ## Input 一个正整数 $n (2 \leq n \leq 10^9)$。 ## Output 如果不能构造，输出一行 `NO`。否则的话就构造出其中一种的合法方案，输出 `YES`，然后让 $\sum^k_{i=1} \frac{a_i}{b_i} = 1 - \frac{1}{n}$，按第二行第一个整数 $k$，接下来 $k$ 行一行两个整数 $a_i$ 和 $b_i(b_i \neq n)$。注意你输出的 $k$ 的范围是 $2 \leq k \leq 10^5$。 [samples] ## Background 翻译自 [NERC 2018](https://neerc.ifmo.ru/archive/2018/neerc-2018-statement.pdf) F 题。 ## Note 对于所有的数据，保证 $2 \leq n \leq 10^9$。对于第一个样例，不存在一种方案使得答案总和为 $\frac{1}{2}$。对于第二个样例，$\frac{1}{2} + \frac{1}{3} = \frac{5}{6}$。

Samples

Input #1

Output #1

NO

Input #2

Output #2

YES
2
1 2
1 3

API Response (JSON)

{
  "problem": {
    "name": "[NERC 2018] Fractions",
    "description": {
      "content": "给你一个整数 $n$，你需要构造出若干个形如 $\\dfrac{a_i}{b_i}$ 的真分数，使得 $\\sum^k_{i=1} \\frac{a_i}{b_i} = 1 - \\frac{1}{n}$，且 $b_i$ 可以整除 $n$。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1750,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9796"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给你一个整数 $n$，你需要构造出若干个形如 $\\dfrac{a_i}{b_i}$ 的真分数，使得 $\\sum^k_{i=1} \\frac{a_i}{b_i} = 1 - \\frac{1}{n}$，且 $b_i$ 可以整除 $n$。\n\n## Input\n\n一个正整数 $n (2 \\leq n \\leq 10^9)$。\n\n## Output\n\n如果不能构造，输出一行 `NO`。\n\n否则的话就构造出其...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments