P9796 [NERC 2018] Fractions

Translated from Problem F of [NERC 2018](https://neerc.ifmo.ru/archive/2018/neerc-2018-statement.pdf).

You are given an integer $n$. You need to construct several proper fractions of the form $\dfrac{a_i}{b_i}$ such that $\sum^k_{i=1} \frac{a_i}{b_i} = 1 - \frac{1}{n}$, and each $b_i$ can divide $n$.

A positive integer $n$ $(2 \leq n \leq 10^9)$.

If it is impossible to construct, output one line `NO`. Otherwise, output one valid solution. Output `YES`, and make $\sum^k_{i=1} \frac{a_i}{b_i} = 1 - \frac{1}{n}$. On the second line output an integer $k$, then in the next $k$ lines output two integers $a_i$ and $b_i$ $(b_i \neq n)$. Note that the range of $k$ you output must satisfy $2 \leq k \leq 10^5$.

For all testdata, it is guaranteed that $2 \leq n \leq 10^9$. For the first sample, there is no solution whose sum equals $\frac{1}{2}$. For the second sample, $\frac{1}{2} + \frac{1}{3} = \frac{5}{6}$. Translated by ChatGPT 5