题解

题目类型：数论 + 分治递归（类欧几里得化简）
核心任务：对每组输入的 m, k 计算一个与“环上步进/淘汰”相关的位置索引；程序最终输出 sol(k-1, m, k) + 1（转为 1-Indexed）。

直观理解：把 0..k-1 放在一个圆环上，从某个起点按步长 m 前进（或做等价的“分组淘汰”计数），问题可被按 g = gcd(m, k) 分组化简到更小的环上，周而复始，直到 g = 1。这一思路与欧几里得算法相似，复杂度近似 O(log k)。

一、函数 sol(l, m, k) 的含义

• 入口调用是 sol(k-1, m, k)，最终答案再加一（从 0-Indexed 变成 1-Indexed）；
• l 可以理解为“当前考虑的目标位置（0..k-1）”，我们需要求出它在“按步长 m 的环形计数/淘汰规则”下的索引；
• 在每一步中，利用 g = gcd(m, k) 对环进行“分块”：把 k 个位置分成 g 个等价类，每个类的规模为 k/g。
  这个分块有两个重要作用：
  1. 若 g = 1（互质），整个环是一个单循环：此时目标位置的索引就是 l 本身（递归基），函数直接返回 l；
  2. 若 g > 1，则环被切成 g 个长度为 k/g 的“块”，我们可以先数清楚目标所在块之前的整块贡献，再把问题压缩到一个更小的环（长度 k/g）上继续求解。

二、递归转移式推导

代码如下（为便于讲解，保留原变量名）：

LL sol(LL l, LL m, LL k){
    LL d = __gcd(m, k);
    if (d == 1) return l;                          // 互质：单循环，索引即 l
    if (l > k/d)                                   // 目标在后半部（越过一个或多个“整块”）
        return m * (k - l) / d 
               + sol((k - m * (k - l)) / d, m, k/d);
    return l;                                      // 目标在前半部：无需跨块，索引仍为 l
}

分情况解释：

1. d = gcd(m, k) = 1（互质）
   环上步长与环长互质，一个大循环覆盖所有元素。
   此时无需再分组化简，索引就是 l，直接返回。

2. d > 1（可分组）
   将 0..k-1 分成 d 个大小为 k/d 的连续“块”。目标位置 l：

   • 若 l <= k/d（目标在“前块”范围内），意味着未跨越整块，索引仍保持为 l；
   • 若 l > k/d（目标在“后块”范围内），那么在到达目标之前，会跨过 (k - l) 个位置，这些跨越可被“整块计数”所消化，其贡献为
     [ \text{整块贡献} = \frac{m \cdot (k - l)}{d} ]
     随后把问题压缩到新环长 k' = k/d 上，新的目标位置变为
     [ l' = \frac{k - m \cdot (k - l)}{d}, ]
     递归求解 sol(l', m, k')，并把“整块贡献”加上去，得到总索引。

这种“先消化整块，再缩小尺度”的思路与 欧几里得算法 的“取整—取余—缩小规模”如出一辙，因此整体复杂度约为 O(log k)。

三、为什么最终输出 sol(k-1, m, k) + 1

• 函数 sol 的返回值对应从 0 开始计数（0-Indexed）；
• 题目最终需要的是 1-Indexed 的位置，因此在输出时要 +1。

四、边界与正确性要点

• 当 gcd(m, k) = 1 时，环是单循环，sol(l, m, k) = l；这正是递归基；
• 当 gcd(m, k) > 1 时，分组化简不会遗漏任何位置：
  • “整块贡献”负责跨越完整等价类；
  • “折算的新 l' 和新 k'”把目标落在了缩小后的环上，信息不丢失；
• 不断重复，k 会被除以 d 逐步缩小，最终必到互质情形结束。

五、复杂度

• 每次递归会把环长 k 缩小到 k / gcd(m, k)，因此递归层数与 k 的质因数分解有关，整体近似 O(log k)；
• 单步仅做常数次的算术与取整，总时间复杂度 O(log k)；
• 代码用 __int128（别名 LL）以防中间乘法溢出，最终输出按 long long 打印（题面数据范围满足）。

代码（与题给一致）

#include<bits/stdc++.h>
# define  LL __int128
using namespace std;
LL sol(LL l,LL m,LL k){
    LL d=__gcd(m,k);
    if(d==1)return l;
    if(l>k/d)return m*(k-l)/d+sol((k-m*(k-l))/d,m,k/d);
    return l;
}
LL n,m,k;
int main (){
    scanf("%d",&n);
    while(n--){
        scanf("%lld %lld",&m,&k);
        printf("%lld\n",sol(k-1,m,k)+1);
    } 
}