問題一覧 > 通常問題

No.1006 Share an Integer

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 240
作問者 : eSeF / テスター : tatyam
13 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) であって、 |f(A)−f(B)| が最小となるようなものを全て求めてください。
組が複数ある場合は、以下の出力形式に倣って、Aの昇順に出力してください。

入力

X

【制約】
・2≤X≤2×106
・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 です。
よって |f(12)−f(9)|=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です。
|f(17)−f(22)|=|f(19)−f(20)|=3 となって、 これらが価値の差が最小な分割になります。
価値の差を 3 未満にすることは出来ません。 　　

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

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