問題一覧 > 通常問題

No.2066 Simple Math !

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 63
作問者 : とりゐとりゐ / テスター : kotatsugamekotatsugame 遭難者遭難者 ygussanyygussany
11 ProblemId : 7967 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-09-02 21:17:01

問題文

正整数 $P,Q,K$ が与えられます．次の条件を満たす正整数 $N$ のうち $K$ 番目に小さいものを求めてください．

  • $N=Px+Qy$ を満たす非負整数の組 $(x,y)$ が存在する．
$T$ 個のテストケースが与えられます．

入力

$T$
$\mathrm{case}_1$
$\vdots$
$\mathrm{case}_T$
各ケースは以下の形式で与えられます． 
$P$ $Q$ $K$

  • $1\leq T\leq 10^4$
  • $1\leq P,Q,K\leq 10^9$
  • 入力は全て整数である

出力

$T$ 行出力してください．

サンプル

サンプル1
入力
4
3 4 1
3 4 2
3 4 3
3 4 4
出力
3
4
6
7

$P=3, Q=4$ の場合を考えます．

  • $N=1$ のとき，$1=3x+4y$ を満たす非負整数の組 $(x,y)$ は存在しません．
  • $N=2$ のとき，$2=3x+4y$ を満たす非負整数の組 $(x,y)$ は存在しません．
  • $N=3$ のとき，$(x,y)=(1,0)$ は $3=3x+4y$ を満たします．
  • $N=4$ のとき，$(x,y)=(0,1)$ は $4=3x+4y$ を満たします．
  • $N=5$ のとき，$5=3x+4y$ を満たす非負整数の組 $(x,y)$ は存在しません．
  • $N=6$ のとき，$(x,y)=(2,0)$ は $6=3x+4y$ を満たします．
  • $N=7$ のとき，$(x,y)=(1,1)$ は $7=3x+4y$ を満たします．
したがって，$P=3, Q=4$ のとき，条件を満たす $N$ は小さい方から $3,4,6,7,\ldots$ です．

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