✅ 春招备战指南 ✅

💡 学习建议：

• 先尝试独立解题
• 对照解析查漏补缺

🧸 题面描述背景等均已深度改编，做法和题目本质基本保持一致。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力

🌸 目前本专栏已经上线200+套真题改编解析，后续会持续更新的

春秋招笔试机考招合集 -> 互联网必备刷题宝典🔗

携程-2026.03.29-开发岗

题目一：字母 a 的位置

字符串长度固定为 ，而且 a 到 e 各出现一次，所以线性扫一遍就结束了，没有任何隐藏点。

难度：Low

题目二：实时榜单

这题容易被“实时排名”吓到，但范围已经给得很小了。维护每个选手每道题的最高分，再扫一遍 名选手统计有多少人总分比 号更高即可。

难度：Low

题目三：字典序最小的扩展串

真正影响字典序的是“连续相同字符形成的整段长度”。按连续相同字符分段后，当前段如果比下一段小，就拿最大的数去拉长它；反之就拿最小的数尽快跨过去。

难度：Mid

题目四：min-gcd 迭代器

当值不超过 时，每一步都在加当前的 ；当值一旦超过 ，就会立刻落进固定点。把同一段 不变的过程整段跳过，复杂度才压得下来。

难度：High

1. 字母 a 的位置

问题描述

小基 拿到了一段长度恰好为 的标签串。

这段字符串只会由 a、b、c、d、e 这五个字符各出现一次组成，顺序可能被打乱。现在需要找出字符 a 出现在第几个位置。

位置从 开始计数。

输入格式

输入一行，一个长度为 的字符串 。

保证字符串中恰好包含一个 a、一个 b、一个 c、一个 d、一个 e。

输出格式

输出一个整数，表示字符 a 的位置。

样例输入 1

abcde

样例输出 1

1

数据范围

• 
• 字符串只由 a、b、c、d、e 组成
• 这五个字符各出现且只出现一次

样例	解释说明
样例1	字符串的第 个字符就是 a，所以答案为 。

题解

这题没有任何隐藏条件，顺着扫一遍字符串就够了。

因为字符串长度固定为 ，所以直接从左到右枚举下标：

1. 如果当前字符不是 a，继续往后看。
2. 一旦遇到 a，立刻输出当前位置编号。

位置从 开始计数，而程序里的下标通常从 开始，所以输出时记得加 。

时间复杂度是 ，也就是常数复杂度。空间复杂度是 。

参考代码

• Python

import sys
input = lambda: sys.stdin.readline().strip()


def solve():
    s = input()

    # 顺着找一遍，遇到 a 就输出 1-based 位置。
    for i, ch in enumerate(s):
        if ch == "a":
            print(i + 1)
            return


if __name__ == "__main__":
    solve()

• Cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    cin >> s;

    // 长度固定为 5，直接线性扫描即可。
    for (int i = 0; i < 5; i++) {
        if (s[i] == 'a') {
            cout << i + 1 << '\n';
            return 0;
        }
    }
    return 0;
}

• Java

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine().trim();

        // 逐个字符检查，找到 a 后输出位置。
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == 'a') {
                System.out.println(i + 1);
                return;
            }
        }
    }
}

2. 实时榜单

问题描述

小基 正在盯一场 赛制训练赛的实时榜单。

比赛里一共有若干道互相独立的题。每名选手对同一道题可以提交很多次，但记分时只保留这道题的最高得分；选手总分等于自己所有题目最高分之和。

现在按时间顺序给出 次提交记录。第 次提交是三个整数 ，表示编号为 的选手在编号为 的题目上拿到了 分。

每处理完一条提交记录，都要输出编号为 的选手当前排名。

排名规则如下：

• 总分更高的选手排名更靠前。
• 总分相同的选手并列，且并列会占用名次。

例如分数从高到低依次为 ，那么对应名次就是 。

输入格式

第一行输入一个整数 ，表示提交记录条数。

接下来 行，每行输入三个整数 ，表示一条提交记录。

输出格式

输出 行。

第 行输出一个整数，表示处理完前 条记录后，编号为 的选手排名。

样例输入 1

10
2 1 0
1 1 80
3 2 100
1 2 60
3 1 40
3 3 60
1 1 90
5 1 100
5 2 100
1 4 50

样例输出 1

1
1
2
1
1
2
2
2
3
1

数据范围

样例	解释说明
样例1	第 次提交后，编号为 的选手在第 题上的最高分从 提升到 ，总分随之变化，因此排名也会重新计算。

题解

题目里的范围其实已经把做法写得很明显了：选手编号最多只有 ，题号最多也只有 。

所以根本不需要平衡树或堆，直接维护两张表就够了：

• best[u][p]：选手 在题目 上的历史最高分。
• sum[u]：选手 当前总分。

当读到一条新提交 时：

1. 如果 ，说明这次没有刷新这道题的最高分，总分不变。
2. 如果 ，就把总分增加 c - best[a][b]，再更新 best[a][b]。

接下来只要统计有多少名选手的总分严格大于 sum[1]。

因为并列要占名次，所以编号为 的选手排名就是：

为什么这样对？

• 总分更高的人一定排在前面。
• 总分相同的人和编号为 并列，不会把他的名次继续往后推。

每次提交后扫描一次 名选手就行，因此总时间复杂度是 ，在这里完全够用。空间复杂度是 。

参考代码

• Python

import sys
input = lambda: sys.stdin.readline().strip()


def solve():
    n = int(input())

    # best[u][p] 记录选手 u 在题目 p 上的最高分。
    best = [[0] * 101 for _ in range(101)]
    total = [0] * 101

    out = []
    for _ in range(n):
        u, p, sc = map(int, input().split())

        # 只有刷新最高分时，总分才会变大。
        if sc > best[u][p]:
            total[u] += sc - best[u][p]
            best[u][p] = sc

        my_score = total[1]
        rank = 1
        for i in range(1, 101):
            if total[i] > my_score:
                rank += 1
        out.append(str(rank))

    print("\n".join(out))


if __name__ == "__main__":
    solve()

• Cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    // best[u][p]：选手 u 在题目 p 上的最高分。
    int best[101][101] = {};
    int sum[101] = {};

    while (n--) {
        int u, p, sc;
        cin >> u >> p >> sc;

        // 如果这次提交更好，就把差值补到总分里。
        if (sc > best[u][p]) {
            sum[u] += sc - best[u][p];
            best[u][p] = sc;
        }

        int rank = 1;
        for (int i = 1; i <= 100; i++) {
            if (sum[i] > sum[1]) {
                rank++;
            }
        }
        cout << rank << '\n';
    }
    return 0;
}

• Java

import java.io.BufferedInputStream;

public class Main {
    static class FastScanner {
        private final byte[] buf = new byte[1 << 16];
        private int len = 0;
        private int ptr = 0;

        private int read() throws Exception {
            if (ptr >= len) {
                len = System.in.read(buf);
                ptr = 0;
                if (len <= 0) {
                    return -1;
                }
            }
            return buf[ptr++];
        }

        int nextInt() throws Exception {
            int c;
            do {
                c = read();
            } while (c <= ' ' && c != -1);
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int x = 0;
            while (c > ' ') {
                x = x * 10 + c - '0';
                c = read();
            }
            return x * sgn;
        }
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner();
        StringBuilder sb = new StringBuilder();

        int n = fs.nextInt();
        int[][] best = new int[101][101];
        int[] sum = new int[101];

        for (int i = 0; i < n; i++) {
            int u = fs.nextInt();
            int p = fs.nextInt();
            int sc = fs.nextInt();

            // 只在刷新题目最高分时更新总分。
            if (sc > best[u][p]) {
                sum[u] += sc - best[u][p];
                best[u][p] = sc;
            }

            int rank = 1;
            for (int j = 1; j <= 100; j++) {
                if (sum[j] > sum[1]) {
                    rank++;
                }
            }
            sb.append(rank).append('\n');
        }

        System.out.print(sb.toString());
    }
}

3. 字典序最小的扩展串

问题描述

小基 有一个长度为 的小写字符串 ，以及一个长度同样为 的正整数数组 。

她可以把数组 任意重排，得到新数组 。随后从左到右执行下面的操作：

• 第 步，在字符串末尾拼接 个字符 。

最终会得到一个新字符串 。

现在希望让 的字典序尽可能小。请输出一种可行的重排结果 。

如果答案不唯一，输出任意一种都可以。

输入格式

第一行输入一个整数 ，表示测试数据组数。

对于每组数据：

• 第一行输入一个整数 。
• 第二行输入一个长度为 的小写字符串 。
• 第三行输入 个整数 。

保证所有测试数据的 之和不超过 。

输出格式

对于每组数据，输出一行 个整数，表示一种能让最终字符串字典序最小的重排结果。

样例输入 1

2
5
aabcd
1 2 3 4 5
3
bac
1 1 2

样例输出 1

4 5 3 2 1
1 2 1

数据范围

• 
• 
• 
• 只包含小写字母
• 所有测试数据的 之和不超过

题解

关键点在于：相邻且相同的字符会直接并成一整段。

例如字符串里出现一段连续的 aaa，无论这三个位置分别分到多少次数，最后在 里看到的都只是：

所以真正影响字典序的，不是单个位置，而是每一段连续相同字符的总长度。

把字符串按连续相同字符压成若干段。设当前段字符是 ，下一段字符是 。

1. 如果

那么当前段越长越好。

因为两种方案在前面完全一样时，先出现分歧的位置一定发生在当前段结束的地方。当前段更长的方案，在那个位置还能继续放字符 ，而另一种方案已经开始放更大的字符 了，所以前者字典序更小。

2. 如果

那么当前段越短越好。

道理正好反过来。当前段一旦缩短，就能更早进入更小的字符 ，字符串会更优。

3. 最后一段

最后一段后面已经没有字符了。若前缀完全相同，那么更短的字符串字典序更小，所以最后一段也应该尽量短。

于是做法就出来了：

1. 先把数组 排序。
2. 从左到右处理每一段连续相同字符。
3. 如果这一段的字符小于下一段字符，就从剩余数字里拿出这一段长度个最大的数。
4. 否则就拿出这一段长度个最小的数。
5. 同一段内部怎么分配都可以，因为它们最终会并成一整段相同字符。

这里用双指针维护当前最小值和最大值即可，时间复杂度是排序的 。

参考代码

• Python

import sys
input = lambda: sys.stdin.readline().strip()


def solve():
    t = int(input())
    out = []

    for _ in range(t):
        n = int(input())
        s = input()
        arr = list(map(int, input().split()))
        arr.sort()

        ans = [0] * n
        l, r = 0, n - 1
        i = 0

        while i < n:
            j = i
            while j < n and s[j] == s[i]:
                j += 1

            cnt = j - i

            # 当前段如果比下一段字符更小，就让这一段尽量长。
            if j < n and s[i] < s[j]:
                vals = arr[r - cnt + 1:r + 1]
                r -= cnt
            else:
                # 当前段更大，或者已经是最后一段，就尽量缩短。
                vals = arr[l:l + cnt]
                l += cnt

            # 同一段内部怎么分都不会改变最终字符串，
            # 这里按升序直接填回去即可。
            for k in range(cnt):
                ans[i + k] = vals[k]

            i = j

        out.append(" ".join(map(str, ans)))

    print("\n".join(out))


if __name__ == "__main__":
    solve()

• Cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int n;
        string s;
        cin >> n >> s;

        vector<long long> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        sort(a.begin(), a.end());

        vector<long long> ans(n);
        int l = 0, r = n - 1;

        for (int i = 0; i < n; ) {
            int j = i;
            while (j < n && s[j] == s[i]) {
                j++;
            }

            int cnt = j - i;
            vector<long long> take;

            // 若这一段字符更小，就把大的数尽量塞给它。
            if (j < n && s[i] < s[j]) {
                for (int k = r - cnt + 1; k <= r; k++) {
                    take.push_back(a[k]);
                }
                r -= cnt;
            } else {
                // 否则拿最小的数，尽快进入下一段字符。
                for (int k = l; k < l + cnt; k++) {
                    take.push_back(a[k]);
                }
                l += cnt;
            }

            for (int k = 0; k < cnt; k++) {
                ans[i + k] = take[k];
            }

            i = j;
        }

        for (int i = 0; i < n; i++) {
            if (i) {
                cout << ' ';
            }
            cout << ans[i];
        }
        cout << '\n';
    }
    return 0;
}

• Java

import java.io.BufferedInputStream;
import java.util.Arrays;

public class Main {
    static class FastScanner {
        private final byte[] buf = new byte[1 << 16];
        private int len = 0;
        private int ptr = 0;

        private int read() throws Exception {
            if (ptr >= len) {
                len = System.in.read(buf);
                ptr = 0;
                if (len <= 0) {
                    return -1;
                }
            }
            return buf[ptr++];
        }

        int nextInt() throws Exception {
            int c;
            do {
                c = read();
            } while (c <= ' ' && c != -1);
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int x = 0;
            while (c > ' ') {
                x = x * 10 + c - '0';
                c = read();
            }
            return x * sgn;
        }

        String next() throws Exception {
            int c;
            do {
                c = read();
            } while (c <= ' ' && c != -1);
            StringBuilder sb = new StringBuilder();
            while (c > ' ') {
                sb.append((char) c);
                c = read();
            }
            return sb.toString();
        }
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner();
        StringBuilder out = new StringBuilder();

        int T = fs.nextInt();
        while (T-- > 0) {
            int n = fs.nextInt();
            String s = fs.next();

            long[] arr = new long[n];
            for (int i = 0; i < n; i++) {
                arr[i] = fs.nextInt();
            }
            Arrays.sort(arr);

            long[] ans = new long[n];
            int l = 0;
            int r = n - 1;

            int i = 0;
            while (i < n) {
                int j = i;
                while (j < n && s.charAt(j) == s.charAt(i)) {
                    j++;
                }

                int cnt = j - i;

                if (j < n && s.charAt(i) < s.charAt(j)) {
                    // 这一段更小，拿最大的 cnt 个数。
                    for (int k = 0; k < cnt; k++) {
                        ans[i + k] = arr[r - cnt + 1 + k];
                    }
                    r -= cnt;
                } else {
                    // 否则拿最小的 cnt 个数。
                    for (int k = 0; k < cnt; k++) {
                        ans[i + k] = arr[l + k];
                    }
                    l += cnt;
                }

                i = j;
            }

            for (int k = 0; k < n; k++) {
                if (k > 0) {
                    out.append(' ');
                }
                out.append(ans[k]);
            }
            out.append('\n');
        }

        System.out.print(out.toString());
    }
}

4. min-gcd 迭代器

问题描述

给定三个正整数 ，定义函数

并记：

现在需要计算 的值。

这里 表示 与 的最大公约数。

输入格式

第一行输入一个整数 ，表示测试数据组数。

接下来 行，每行输入三个整数 。

输出格式

输出 行，每行一个整数，表示对应测试数据的答案。

样例输入 1

4
7 3 4
10 2 3
3 10 2
6 50 100

样例输出 1

4
4
6
100

数据范围

样例	解释说明
样例1	以第一组为例：，之后再次代入都会得到 ，所以无论继续迭代多少次，答案都还是 。

题解

这题最重要的分界点就是 和 的大小关系。

1. 当 时会立刻进入不动点

这时

而 ，所以下一步还是这个值。也就是说，只要某次迭代后已经超过了 ，答案马上就固定住了。

2. 当 时，式子会变成

设

那么一定有 。

在接下来这段时间里，只要 还保持为 ，每一步都会让 增加 ，也就是让 增加 。

所以问题变成了：

• 从当前的 开始不断加 ；
• 什么时候第一次让 和 不再互质？
• 或者什么时候第一次让 超过 ？

3. 如何一次跳过很多步

只要 的某个质因子 整除新的 ，那么 就会变大，原来的 也会跟着变大。

因此只要枚举 的不同质因子，就能算出“距离下一次 变化还差多少步”：

• 若当前 ，那么最早在 p - y % p 步后会碰到一个被 整除的值。

同时，还要算出“多少步后会第一次超过 ”。两者取更小值，就是这一个阶段可以整段跳过的步数。

4. 跳的次数为什么很少

每次真正发生 变化时，新的公约数至少会乘上一个不小于 的因子，所以 至少翻倍。

而 ，因此这样的变化次数最多只有 次。

所以整道题的流程是：

1. 先分解出 的所有不同质因子。
2. 对每组数据维护当前的 、剩余步数 n 和当前 gcd。
3. 不断按阶段跳跃，直到步数用完，或者已经进入固定点。

时间复杂度约为“分解质因子 + 若干次跳跃”。跳跃次数很少，真正的核心开销在分解上。

参考代码

• Python

import sys
input = lambda: sys.stdin.readline().strip()


def build_primes(limit):
    is_prime = [True] * (limit + 1)
    is_prime[0] = is_prime[1] = False
    ps = []
    for i in range(2, limit + 1):
        if is_prime[i]:
            ps.append(i)
            if i * i <= limit:
                step = i
                start = i * i
                is_prime[start:limit + 1:step] = [False] * (((limit - start) // step) + 1)
    return ps


PRIMES = build_primes(10**6)
FACT_CACHE = {}


def distinct_prime_factors(x):
    if x in FACT_CACHE:
        return FACT_CACHE[x]

    n = x
    res = []
    for p in PRIMES:
        if p * p > n:
            break
        if n % p == 0:
            res.append(p)
            while n % p == 0:
                n //= p
        if n == 1:
            break
    if n > 1:
        res.append(n)

    FACT_CACHE[x] = res
    return res


def solve_one(a, b, k):
    primes = distinct_prime_factors(b)

    # 已经大于 b 时，一步后就会进入固定点。
    if a > b:
        return b + __import__("math").gcd(a, b)

    x = a
    left = k

    while left > 0 and x <= b:
        d = __import__("math").gcd(x, b)

        # x == b 时，下一步一定到 2b，之后保持不变。
        if x == b:
            return 2 * b

        m = b // d
        y = x // d

        # 跳到第一次超过 b 的步数。
        to_out = m - y + 1

        # 跳到 gcd 首次变大的步数。
        to_grow = to_out
        for p in primes:
            if m % p == 0:
                step = p - (y % p)
                if step < to_grow:
                    to_grow = step

        step = min(to_out, to_grow)

        if left <= step:
            return x + left * d

        x += step * d
        left -= step

        if x > b:
            return b + d

    return x


def solve():
    t = int(input())
    out = []
    for _ in range(t):
        a, b, n = map(int, input().split())
        out.append(str(solve_one(a, b, n)))
    print("\n".join(out))


if __name__ == "__main__":
    solve()

• Cpp

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;

vector<int> build_primes(int limit) {
    vector<int> primes;
    vector<int> is_prime(limit + 1, 1);
    is_prime[0] = is_prime[1] = 0;
    for (int i = 2; i <= limit; i++) {
        if (is_prime[i]) {
            primes.push_back(i);
            if (1LL * i * i <= limit) {
                for (int j = i * i; j <= limit; j += i) {
                    is_prime[j] = 0;
                }
            }
        }
    }
    return primes;
}

vector<int> PRIMES = build_primes(1000000);
unordered_map<long long, vector<long long>> cache_pf;

vector<long long> distinct_prime_factors(long long x) {
    if (cache_pf.count(x)) {
        return cache_pf[x];
    }

    long long n = x;
    vector<long long> res;
    for (int p : PRIMES) {
        if (1LL * p * p > n) {
            break;
        }
        if (n % p == 0) {
            res.push_back(p);
            while (n % p == 0) {
                n /= p;
            }
        }
        if (n == 1) {
            break;
        }
    }
    if (n > 1) {
        res.push_back(n);
    }

    return cache_pf[x] = res;
}

long long solve_one(long long a, long long b, long long k) {
    vector<long long> primes = distinct_prime_factors(b);

    // 已经超过 b 时，一步之后就稳定在固定点。
    if (a > b) {
        return b + gcd(a, b);
    }

    long long x = a;
    long long left = k;

    while (left > 0 && x <= b) {
        long long d = gcd(x, b);

        // x == b 时，下一次一定到 2b。
        if (x == b) {
            return 2 * b;
        }

        long long m = b / d;
        long long y = x / d;

        long long to_out = m - y + 1;
        long long to_grow = to_out;

        for (long long p : primes) {
            if (m % p == 0) {
                long long step = p - (y % p);
                to_grow = min(to_grow, step);
            }
        }

        long long step = min(to_out, to_grow);

        if (left <= step) {
            return x + left * d;
        }

        x += step * d;
        left -= step;

        if (x > b) {
            return b + d;
        }
    }

    return x;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        long long a, b, n;
        cin >> a >> b >> n;
        cout << solve_one(a, b, n) << '\n';
    }
    return 0;
}

• Java

import java.io.BufferedInputStream;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class Main {
    static class FastScanner {
        private final byte[] buf = new byte[1 << 16];
        private int len = 0;
        private int ptr = 0;

        private int read() throws Exception {
            if (ptr >= len) {
                len = System.in.read(buf);
                ptr = 0;
                if (len <= 0) {
                    return -1;
                }
            }
            return buf[ptr++];
        }

        long nextLong() throws Exception {
            int c;
            do {
                c = read();
            } while (c <= ' ' && c != -1);
            long sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long x = 0;
            while (c > ' ') {
                x = x * 10 + c - '0';
                c = read();
            }
            return x * sgn;
        }
    }

    static List<Integer> buildPrimes(int limit) {
        boolean[] isPrime = new boolean[limit + 1];
        for (int i = 2; i <= limit; i++) {
            isPrime[i] = true;
        }
        List<Integer> primes = new ArrayList<>();
        for (int i = 2; i <= limit; i++) {
            if (isPrime[i]) {
                primes.add(i);
                if ((long) i * i <= limit) {
                    for (int j = i * i; j <= limit; j += i) {
                        isPrime[j] = false;
                    }
                }
            }
        }
        return primes;
    }

    static final List<Integer> PRIMES = buildPrimes(1_000_000);
    static final HashMap<Long, List<Long>> FACT_CACHE = new HashMap<>();

    static List<Long> distinctPrimeFactors(long x) {
        if (FACT_CACHE.containsKey(x)) {
            return FACT_CACHE.get(x);
        }

        long n = x;
        List<Long> res = new ArrayList<>();
        for (int p : PRIMES) {
            long pp = 1L * p * p;
            if (pp > n) {
                break;
            }
            if (n % p == 0) {
                res.add((long) p);
                while (n % p == 0) {
                    n /= p;
                }
            }
            if (n == 1) {
                break;
            }
        }
        if (n > 1) {
            res.add(n);
        }

        FACT_CACHE.put(x, res);
        return res;
    }

    static long gcd(long a, long b) {
        while (b != 0) {
            long t = a % b;
            a = b;
            b = t;
        }
        return a;
    }

    static long solveOne(long a, long b, long k) {
        List<Long> primes = distinctPrimeFactors(b);

        // 已经超过 b 时，一步后立刻进入固定点。
        if (a > b) {
            return b + gcd(a, b);
        }

        long x = a;
        long left = k;

        while (left > 0 && x <= b) {
            long d = gcd(x, b);

            if (x == b) {
                return 2L * b;
            }

            long m = b / d;
            long y = x / d;

            long toOut = m - y + 1;
            long toGrow = toOut;

            for (long p : primes) {
                if (m % p == 0) {
                    long step = p - (y % p);
                    if (step < toGrow) {
                        toGrow = step;
                    }
                }
            }

            long step = Math.min(toOut, toGrow);

            if (left <= step) {
                return x + left * d;
            }

            x += step * d;
            left -= step;

            if (x > b) {
                return b + d;
            }
        }

        return x;
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner();
        StringBuilder out = new StringBuilder();

        int T = (int) fs.nextLong();
        for (int i = 0; i < T; i++) {
            long a = fs.nextLong();
            long b = fs.nextLong();
            long n = fs.nextLong();
            out.append(solveOne(a, b, n)).append('\n');
        }

        System.out.print(out.toString());
    }
}