問題一覧 > 通常問題

No.2066 Simple Math !

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

問題文

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

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

入力

TT
case1\mathrm{case}_1
⋮\vdots
caseT\mathrm{case}_T
各ケースは以下の形式で与えられます． 
PP QQ KK

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

出力

TT 行出力してください．

サンプル

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

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

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

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