問題一覧 > 通常問題

No.2358 xy+yz+zx=N

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 （複数の解が存在する可能性があります）
タグ : / 解いたユーザー数 142
作問者 : 遭難者遭難者 / テスター : AngrySadEightAngrySadEight 👑 ygussanyygussany
3 ProblemId : 9526 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-06-23 23:37:58

問題文

正整数 $N$ が与えられます。

$xy+yz+zx=N$ を満たす非負整数の組 $(x,y,z)$ を全て求めてください。

制約

  • $1\le N\le 10^7$

入力

$N$

出力

以下の形式で出力してください。 

$T$
$x_1$ $y_1$ $z_1$
$x_2$ $y_2$ $z_2$
$\vdots$
$x_T$ $y_T$ $z_T$
ただし、 $T$ は条件を満たす非負整数の組の個数で、 $(x_i,y_i,z_i)$ は条件を満たす非負整数の組である必要があります。

また、 $i\neq j$ なら $(x_i,y_i,z_i) \neq (x_j,y_j,z_j)$ を満たしていなければなりません。

以上の条件を満たしているのであれば整数の組をどの順番で出力しても構いません。

サンプル

サンプル1
入力
2
出力
6
0 1 2
0 2 1
1 0 2
1 2 0
2 0 1
2 1 0

$(x,y,z)=(0,1,2)$ の並べ替えが条件を満たします。

この例では辞書順に出力していますが、必ずしも辞書順で出力する必要はありません。

サンプル2
入力
5
出力
9
0 1 5
1 0 5
5 0 1
1 5 0
0 5 1
2 1 1
1 1 2
5 1 0
1 2 1

サンプル3
入力
97
出力
15
0 1 97
0 97 1
1 0 97
1 1 48
1 6 13
1 13 6
1 48 1
1 97 0
6 1 13
6 13 1
13 1 6
13 6 1
48 1 1
97 0 1
97 1 0

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