No.1006 Share an Integer

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 143
作問者 : eSeFeSeF / テスター : tatyamtatyam
8 ProblemId : 3984 / 出題時の順位表
問題文最終更新日: 2020-03-06 00:20:55

問題文

忍さんはイギリスで正整数 $X$ を拾い、アリスさんにプレゼントしました。
しかし二人は仲良しなので、アリスさんはこれを仲良く分ける事にしました。
約数が沢山あると仲も割り切れてしまう気がするので、 整数 $N$ の価値 $f(N)$ を以下のように定めました。

$f(N)=N-d(N)$ ただし、$d(N)$ は $N$ の正の約数の個数

二人のために、整数 $X$ の平等な分割を全て求めてください。
正確には、 $X=A+B$ を満たす正整数の組 $(A,B)$ であって、 $\left| f(A)-f(B)\right| $ が最小となるようなものを全て求めてください。
組が複数ある場合は、以下の出力形式に倣って、Aの昇順に出力してください。

入力

$X$

【制約】
・$2\le X\le 2\times 10^6$
・$X$ は整数である。

出力

最も平等な $X$ の分割方法となるような、整数の組 $(A,B)$ を全て出力せよ。
具体的には、組が $n$ 個存在する場合、 $n$ 行出力し、各行に $A,B$ をこの順序で空白区切りで出力せよ。
ただし、この時 $A$ について昇順になるように出力すること。

サンプル

サンプル1
入力
21
出力
9 12
12 9

12 の正の約数は 1,2,3,4,6,12 の 6 つあるので $f(12)=12-6=6$ です。
9 の正の約数は 1,3,9 の 3 つあるので $f(9)=9-3=6$ です。
よって $\left| f(12)-f(9)\right| =0$ となり、$(9,12),(12,9)$ という分割で価値の差が最小となります。
これ以外に価値の差が最小の 0 となる組は存在しません。

サンプル2
入力
39
出力
17 22
19 20
20 19
22 17

$f(17)=17-2=15$、$f(19)=19-2=17$、$f(20)=20-6=14$、$f(22)=22-4=18$です。
$\left| f(17)-f(22)\right| =\left| f(19)-f(20)\right| =3$ となって、 これらが価値の差が最小な分割になります。
価値の差を 3 未満にすることは出来ません。   

サンプル3
入力
489
出力
237 252
241 248
243 246
244 245
245 244
246 243
248 241
252 237

提出するには、Twitter または、GitHubもしくは右上の雲マークをクリックしてアカウントを作成してください。