No.1006 Share an Integer
タグ : / 解いたユーザー数 238
作問者 :
eSeF
/ テスター :
tatyam
問題文
忍さんはイギリスで正整数 $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、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。