問題一覧 > 通常問題

No.1409 Simple Math in yukicoder

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 （複数の解が存在する可能性があります）
タグ : / 解いたユーザー数 54
作問者 : PCTprobabilityPCTprobability / テスター : akakimidoriakakimidori kaagekaage
5 ProblemId : 5619 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-02-26 21:32:42

問題文

正整数 $v,x$ が与えられます。ただし、$xv+1$ は素数であることが保証されます。以下の条件を満たす正整数列 $a_1,a_2,...,a_x$ を $1$ 個求めてください。

  • $1$ $\le$ $a_1$ $<$ $a_2$ $<$ $...$ $<$ $a_x$ $\le$ $xv$
  • $1$ 以上 $x$ 未満の全ての正整数 $k$ に対して、\( \displaystyle \sum_{i=1}^{x}a_i^k \) は $xv+1$ で割り切れる。
  • \( \displaystyle \sum_{i=1}^{x}a_i^x \) は $xv+1$ で割ると $x$ 余る。

数列 $a$ としてあり得るものを空白区切りで出力してください。解が必ず存在することが保証されます。

この問題は $T$ 個テストケースが与えられます。

入力

$T$
テストケース $1$
テストケース $2$
$.$$.$$.$
テストケース $T$
それぞれのテストケースは以下の形式で与えられます。 
$v$ $x$

  • 入力は全て正整数である。
  • $1 \le T,v \le 1000$
  • $1 \le x \le 100$
  • $xv+1$ は素数である。

出力

$T$ 行出力してください。$i$ 行目にはテストケース $i$ の解答を出力してください。

サンプル

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

この場合、$xv+1=3$ となります。この時 $a_1=1,a_2=2$ は、 $1 \le a_1 < a_2 \le 2$ かつ $1+2≡0 \bmod 3$ かつ $1^2+2^2≡2 \bmod 3$ を満たすので解になります。

サンプル

サンプル1
入力
3
2 6
2 1
6 7
出力
1 3 4 9 10 12
1
1 4 11 16 21 35 41

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