小美的外卖订单编号【牛客tracker 每日一题】

小美的外卖订单编号

时间限制：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×104
• 1 ≤ 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)modm+1
• 适用范围：对所有m ≥ 1 , x ≥ 1 m \ge 1, x \ge 1m≥1,x≥1成立。当m = 1 m = 1m=1时，所有订单编号恒为1 11。

2. 算法实现

1. 读入询问次数q qq。
2. 对每组( 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)modm+1直接给出答案。无需存储序列或模拟过程。

代码简要说明

• 读入q qq，循环处理每组( m , x ) (m, x)(m,x)。
• 用(x - 1) % m + 1计算并输出编号。

代码内容

#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll q;cin>>q;while(q--){ll m,x;cin>>m>>x;cout<<(x-1)%m+1<<'\n';}return0;}