← 返回题目列表

AtCoder · stpc2025_2_g

G. 团队划分

中文机器翻译题面 查看原题

配点 : 100 点

問題文

正整数 A, B, L, R 。 对于

x = L, L+1, \dots, R 关于 ,请回答以下问题 f(x) 。

将举办编程竞赛。参赛者 x 有人。

x 将人的竞技者 A 人或 B 人分成几个队伍。每个运动员必须恰好 1 个队伍。

此时,请求队伍数的最小値。但是,如果无法分队,请求答案为 10^{100} 。

\displaystyle\max_{L \le x \le R} f(x) 。但是,当答案为 10^{100} 时,-1 。

T 给出若干测试用例,请分别求出答案。

制約

  • 所有输入均为整数
  • 1 \leq T \leq 10^5
  • 1 \leq A, B \leq 10^9
  • 1 \leq L \leq R \leq 10^{18}

入力

输入按以下格式给出。

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

在这里,\mathrm{case}_i 是 您也可以写 i 个测试用例。每个测试用例均按以下格式给出。

A B L R

出力

T 个测试用例的答案请以换行分隔输出。


入力例 1

3
3 2 1 7
3 5 10 20
37 518946 448700728 617638174

出力例 1

-1
5
520098

关于第一个案例,当参加的大学生人数为 1 人时,2 人队伍也好,3 人队伍也好,都无法分组。

2 关于第一个案例,当参加的大学生人数为 19 人时,3 人员团队 3 津托 5 人员团队 2 分成是最合适的,此时,总队伍数为 5 。在参加大学生人数少于 10 人以上 20 人的任何场合,也可以分成少于5 个的团队,所以答案是 5 。 对于