← 返回题目列表

Codeforces · 1089/F

F. 分数

中文机器翻译题面 查看原题

给你一个正整数$$$n$$$。

对于某些 $$$k$$$ 查找分数序列 $$$\frac{a_i}{b_i}$$$, $$$i = 1 \ldots k$$$ (其中 $$$a_i$$$ 和 $$$b_i$$$ 是正整数),使得:

$$\begin{cases} \text{$b_i$ 除 $n$, $1 \lt b_i \lt n$ for $i = 1 \ldots k$} \\ \text{$1 \le a_i \lt b_i$ for $i = 1 \ldots k$} \\ \text{$\sum\limits_{i=1}^k \frac{a_i}{b_i} = 1 - \frac{1}{n}$} \end{案例}$$

输入

输入由单个整数 $$$n$$$ ($$$2 \le n \le 10^9$$$) 组成。

输出

在第一行打印“是“如果存在这样的分数序列或”NO”否则。

如果存在这样的序列,则下一行应包含以下格式的序列描述。

第二行应包含整数 $$$k$$$ ($$$1 \le k \le 100\,000$$$) — 序列中的元素数量。保证如果存在这样的序列,则存在长度至多$$$100\,000$$$的序列。

接下来的 $$$k$$$ 行应包含序列的分数,每行上有两个整数 $$$a_i$$$ 和 $$$b_i$$$。

示例

输入
复制

2

输出
复制

NO

输入
复制

6

输出
复制

YES
2
1 2
1 3

注意

在第二个示例中,有一个序列 $$$\frac{1}{2}, \frac{1}{3}$$$ 使得 $$$\frac{1}{2} + \frac{1}{3} = 1 - \frac{1}{6}$$$。