把 1…N 的数按模 d 的余数分组。若两张卡余数分别为 r 与 d−r(含 0 与 d/2 的自配对),它们之和能被 d 整除。
问题等价于:求一个最大规模的集合 α(N,d),使得集合中任意两数之和都 不能 被 d 整除;则答案 K(N,d) = α(N,d) + 1(抽屉原理)。
记 q = ⌊N/d⌋,rem = N % d。在 1…N 中:
q 个;1..rem 的每个余数组有 q+1 个;rem+1..d-1 的每个余数组有 q 个。构造最大集合的规则(贪心/计数):
某超市举办“盲盒选品”活动,盲盒内装有编号 1 到 N 的 N 个商品卡片。活动规则要求:若选到的卡片中存在两种编号之和能被 d 整除,则可额外兑换一份礼品。
顾客希望知道“保底门槛”——即确定最小的选卡数量 K ,使得无论顾客选择哪 K 张不同的卡片,都必然存在两张卡片的编号之和能被 d 整除(触发兑换条件)。这个“保底门槛” K 就是需要计算的 K(N,d) 。
每个测试文件均包含多组测试数据,第一行输入一个整数 T(1≤T≤2×105) 代表数据组数,每组测试数据描述如下:
接下来 T 行,每行输入两个整数 N,d(1<d<N≤1018) 。
输出 T 行,每行一个整数,表示答案 K(N,d) 。
输入
3
7 3
10 2
10 3
输出
5
3
6