T 组数据，每一组数据给定 l，r，x，我们试求：闭区间 l 到 r 的所有整数对 x 做整除所有数取最大公约数。 输入格式: 第一行输入一个正整数 T，表示数据组数。 对于每一组数据，输入一行三个正整数 l，r，x 以空格隔开。 输出格式: 对于每一组数据，输出一行，一个正整数表示答案。 输入样例: 4 3 6 1 8 11 4 4 4 3 7 16 2 输出样例: 1 2 1 1 ###取值范围 对于所有数据， 1 ≤ x ≤ l ≤ r ≤ 10 18 ， 1 ≤ T ≤ 10 用C++语言解答

• 求闭区间内整数的最大公约数。

算法思路

• 暴力法：枚举闭区间内所有整数，计算它们对x的最大公约数，取最大值。3
• 优化法：利用最大公约数的性质，减少计算量。27

实现步骤

• 输入处理：读取T组数据，每组包括l，r，x。5
• 算法实现：
  • 对于每组数据，初始化最大公约数为1。
  • 遍历闭区间[l, r]内每个整数i。
  • 计算i和x的最大公约数gcd(i, x)。
  • 更新最大公约数为当前最大公约数和gcd(i, x)中的较大者。
• 输出结果：对于每组数据，输出计算得到的最大公约数。

#include <iostream>
#include <algorithm>
using namespace std;

// 计算最大公约数
int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

int main() {
    int T, l, r, x;
    cin >> T;
    while (T--) {
        cin >> l >> r >> x;
        int max_gcd = 1;
        for (int i = l; i <= r; i++) {
            max_gcd = max(max_gcd, gcd(i, x));
        }
        cout << max_gcd << endl;
    }
    return 0;
}