字节跳动软件开发笔试

给定四个正整数a, b, l, r，小红希望你在[l, r]区间内寻找一个正整数x，满足x恰好是a或b其中一个的倍数(不能同时为a和b的倍数)。你能帮帮她吗?

共有q次询问。

输入描述

第一行输入一个正整数q，代表询问次数。

接下来的q行，每行输入四个正整数a, b, l, r，代表一次询问。

1 ≤q≤ 10^5

1 ≤ a, b ≤ 10^9

1 ≤l≤r< 10^4

输出描述

输出q行，如果区间内不存在合法的数，请输出-1;否则输出任意一个合法解

示例 1

输入

3

2 3 5 9

5 4 7 10

4 6 9 15

输出

9

8

-1

说明

第一组询问，输出8、9均可通过本题

第二组询问，输出10也是可以的。

第三组询问，显然无解。

#include <iostream>
#include <algorithm>

using namespace std;

// 辗转相除法求最大公约数
long long gcd(long long a, long long b) {
    while (b != 0) {
        long long t = b;
        b = a % b;
        a = t;
    }
    return a;
}

// 计算最小公倍数
long long lcm(long long a, long long b) {
    return a / gcd(a, b) * b; // 防止溢出
}

int main() {
    int q;
    cin >> q;

    while (q--) {
        long long a, b, l, r;
        cin >> a >> b >> l >> r;

        long long lcm_ab = lcm(a, b);
        long long result = -1;

        // 找到大于等于 l 的最小 a 的倍数和 b 的倍数
        long long min_a = ((l + a - 1) / a) * a;
        long long min_b = ((l + b - 1) / b) * b;

        // 从 min_a 和 min_b 开始检查，直到 r
        for (long long x = min(min_a, min_b); x <= r; x++) {
            if ((x % a == 0 || x % b == 0) && x % lcm_ab != 0) {
                result = x;
                break;
            }
        }

        cout << result << endl;
    }

    return 0;
}

小红定义一个字符串的权值为:相同连续字符组成的尽可能长的连续段数量。例如，"aabbccc"的权值为 3，因为"aa"+"bb"+"ccc"，共有3个连续段。

小红拿到了一个字符串，她有若干次询问，每次询问截取一个连续子串，希望你回答这个连续子串的权值。你能帮帮她吗?

输入描述

第一行输入两个正整数n，q，代表字符串长度和询问次数

第二行输入一个长度为n的、仅由小写字母组成的字符串。

接下来的q行，每行输入两个正整数li, ri，代表查询的是第li个字符到第ri个字符组成的

子串。

1 <=n, q<=10^5

1 <= li <= ri <= n

输出描述

输出q行，每行输出一个正整数，代表查询的子串的权值。

示例 1

输入

7 3

aabbccc

1 7

2 4