分数: 400 点
问题陈述
N 队伍正在参加团体将棋锦标赛。 每个团队由 M 玩家。 本次比赛采用循环赛制,共有 \frac{N(N-1)}{2} 已进行比赛。 每场比赛中, M 每支队伍的玩家都是随机匹配的,并且总是一名玩家获胜而另一名玩家失败。 所有比赛结束后,每位球员都将准确地完成比赛 N-1 场比赛,赢得所有比赛的玩家将获得完美战绩奖。 找出可以获得完美记录奖的最大可能玩家人数。
解决 T 每个输入文件的测试用例。 一个输入文件中的
约束
- 1 \leq T \leq 2 \times 10^5
- 2 \leq N \leq 10^9
- 1 \leq M \leq 10^9
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
T case_1 case_2 \vdots case_T
每个案例均按以下格式给出:
N M
输出
总共输出答案 T 行。 的 t- 第行应包含能够获得完美记录奖的最大可能数量的玩家 t- 第一个测试用例。
示例输入 1
2 3 3 5 1
示例输出 1
4 1
对于第一个测试用例,
假设以下 3 参加比赛的队伍:
团队 T:玩家 T_1,T_2,T_3
团队 W:玩家 W_1,W_2,W_3
团队 R:玩家 R_1,R_2,R_3
并假设出现以下结果:
- 球队之间的比赛 T 和团队 W
- 之间的游戏 T_1 和 W_1: W_1 获胜
- 之间的游戏 T_2 和 W_2: W_2 获胜
- 之间的游戏 T_3 和 W_3: T_3 获胜
- 球队之间的比赛 T 和团队 R
- 之间的游戏 T_1 和 R_3: T_1 获胜
- 之间的游戏 T_2 和 R_1: R_1 获胜
- 之间的游戏 T_3 和 R_2: T_3 获胜
- 球队之间的比赛 W 和团队 R
- 之间的游戏 W_1 和 R_3: R_3 获胜
- 之间的游戏 W_2 和 R_2: R_2 获胜
- 之间的游戏 W_3 和 R_1: W_3 获胜
然后,只有玩家 T_3 来自团队 T 荣获完美唱片奖。
在这种情况下,可以获得完美记录奖的玩家的最大可能数量是 4.