小美的外卖订单编号时间限制1 秒空间限制256 MB网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述美团商家的订单编号初始值为1 11。每当发起一笔新订单时编号自动加1 11。为了防止编号无限增大商家设置了一个编号上限m mm一旦当前订单编号加1 11后大于m mm下一个订单的编号将重新从1 11开始。给定q qq次询问第i ii次询问给出一对整数( m i , x i ) (m_i, x_i)(mi​,xi​)请你计算在编号上限为m i m_imi​的情况下第x i x_ixi​个订单的编号是多少。输入描述第一行输入一个整数q ( 1 ≤ q ≤ 5 × 10 4 ) q\ (1 \le q \le 5 \times 10^4)q(1≤q≤5×104)表示询问的数量。接下来q qq行第i ii行包含两个整数m i , x i ( 1 ≤ m i , x i ≤ 10 9 ) m_i, x_i\ (1 \le m_i, x_i \le 10^9)mi​,xi​(1≤mi​,xi​≤109)表示第i ii次询问的参数。输出描述对于每个询问输出一行一个整数表示第x i x_ixi​个订单的编号。示例示例 1输入4 2 3 5 17 8 2 4 4输出1 2 2 4说明以第一组询问( m , x ) ( 2 , 3 ) (m, x) (2, 3)(m,x)(2,3)为例订单编号序列为1 , 2 , 1 , 2 , … 1, 2, 1, 2, \dots1,2,1,2,…第3 33个编号为1 11故输出1 11。其余询问均可按相同规则得到答案。数据范围与提示1 ≤ q ≤ 5 × 10 4 1 \le q \le 5 \times 10^41≤q≤5×1041 ≤ m i , x i ≤ 10 9 1 \le m_i, x_i \le 10^91≤mi​,xi​≤109编号按1 ∼ m 1 \sim m1∼m循环本质上是求x xx在模m mm意义下的结果。注意当x xx恰好是m mm的倍数时答案应为m mm而不是0 00。解题思路本题本质上是循环周期计数问题要求计算编号在1 ∼ m 1 \sim m1∼m之间循环时第x xx个订单对应的编号。利用模运算可以直接得出结果无需模拟生成序列。1. 问题等价转化编号规则初始编号为1 11之后每来一个订单编号加1 11一旦超过m mm则重置为1 11。因此编号序列为1 , 2 , 3 , … , m , 1 , 2 , … 1, 2, 3, \dots, m, 1, 2, \dots1,2,3,…,m,1,2,…数学表示将编号整体减1 11得到0 , 1 , 2 , … , m − 1 0, 1, 2, \dots, m-10,1,2,…,m−1的循环序列此时问题变为求该序列的第x xx项从第1 11项开始即( x − 1 ) m o d m (x-1) \bmod m(x−1)modm最后再加1 11还原。因此第x xx个订单的编号为( x − 1 ) m o d m 1 (x - 1) \bmod m 1(x−1)modm1适用范围对所有m ≥ 1 , x ≥ 1 m \ge 1, x \ge 1m≥1,x≥1成立。当m 1 m 1m1时所有订单编号恒为1 11。2. 算法实现读入询问次数q qq。对每组( m , x ) (m, x)(m,x)直接计算ans (x - 1) % m 1输出ans。3. 复杂度分析时间复杂度每个询问O ( 1 ) O(1)O(1)总复杂度O ( q ) O(q)O(q)q ≤ 5 × 10 4 q \le 5\times 10^4q≤5×104极快。空间复杂度O ( 1 ) O(1)O(1)仅需常数个变量。总结将1 11基的循环编号映射为0 00基的模运算公式( x − 1 ) m o d m 1 (x-1) \bmod m 1(x−1)modm1直接给出答案。无需存储序列或模拟过程。代码简要说明读入q qq循环处理每组( m , x ) (m, x)(m,x)。用(x - 1) % m 1计算并输出编号。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll q;cinq;while(q--){ll m,x;cinmx;cout(x-1)%m1\n;}return0;}