問題一覧 > 通常問題

No.2066 Simple Math !

レベル : / AI推定難易度 : 2200 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 67
作問者 : とりゐ / テスター : kotatsugame 👑 qand ygussany
お気に入りにしたユーザー ProblemId : 7967 / 自分の提出
問題文最終更新日: 2022-09-02 21:17:01
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 359 (順位表) の他の問題:

Problem Statement

You are given positive integers $P,Q,K$. Find the $K$-th smallest positive integer $N$ satisfying the following condition.

  • There exists a pair of non-negative integers $(x,y)$ such that $N=Px+Qy$.
You are given $T$ test cases.

Input

$T$
$\mathrm{case}_1$
$\vdots$
$\mathrm{case}_T$
Each case is given in the following format.
$P$ $Q$ $K$

  • $1\leq T\leq 10^4$
  • $1\leq P,Q,K\leq 10^9$
  • All inputs are integers.

Output

Print $T$ lines.

Sample

Sample 1
Input
4
3 4 1
3 4 2
3 4 3
3 4 4
Output
3
4
6
7

Consider the case $P=3, Q=4$.

  • When $N=1$, there is no pair of non-negative integers $(x,y)$ satisfying $1=3x+4y$.
  • When $N=2$, there is no pair of non-negative integers $(x,y)$ satisfying $2=3x+4y$.
  • When $N=3$, $(x,y)=(1,0)$ satisfies $3=3x+4y$.
  • When $N=4$, $(x,y)=(0,1)$ satisfies $4=3x+4y$.
  • When $N=5$, there is no pair of non-negative integers $(x,y)$ satisfying $5=3x+4y$.
  • When $N=6$, $(x,y)=(2,0)$ satisfies $6=3x+4y$.
  • When $N=7$, $(x,y)=(1,1)$ satisfies $7=3x+4y$.
Therefore, when $P=3, Q=4$, the values of $N$ satisfying the condition are $3,4,6,7,\ldots$ in ascending order.

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