← 返回题目列表

AtCoder · arc203_a

A. 所有获奖者

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

分数: 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.