No.2449 square_permutation
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 30
作問者 :
hiryuN
/ テスター :
stoq
タグ : / 解いたユーザー数 30
作問者 :
hiryuN
/ テスター :
stoq
問題文最終更新日: 2023-10-05 19:14:08
問題文
正の整数 $N$ が与えられます。 以下の条件を満たす $(1, 2, ..., N)$ の順列 $P$ のうち、辞書順で最も大きいものを出力してください。
- $1 \leq i \leq N$ を満たすすべての $i$ に対して $P_i \times i$ が平方数になる。
尚、本制約下では条件を満たす順列が $1$ つ以上存在することが証明できます。
入力
$N$
- $1 \leq N \leq 3×10^5$
- $N$ は正の整数
出力
条件を満たす順列 $P$ のうち辞書順で最も大きいものをスペース区切りで出力してください。
サンプル
サンプル1
入力
3
出力
1 2 3
1 2 3 は条件を満たす唯一の順列であるため、これを出力してください。
サンプル2
入力
6
出力
4 2 3 1 5 6
条件を満たす順列は
1 2 3 4 5 6 と
4 2 3 1 5 6
の $2$ 種類があるため、より辞書順で大きい後者を出力してください。
サンプル3
入力
20
出力
16 18 12 9 20 6 7 8 4 10 11 3 13 14 15 1 17 2 19 5
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。