4199. 公约数-公约数模版题

给定两个正整数 a 和 b。

你需要回答 q个询问。

每个询问给定两个整数 l,r，你需要找到最大的整数 x，满足：

1. x 是 a 和 b 的公约数。
2. l≤x≤r。

输入格式

第一行包含两个整数 a,b。

第二行包含一个整数 q。

接下来 q 行，每行包含两个整数 l,r。

输出格式

每个询问输出一行答案，即满足条件的最大的 xx，如果询问无解，则输出 −1。

数据范围

前六个测试点满足 1≤a,b≤100，1≤q≤20。
所有测试点满足 1≤a,b≤109，1≤q≤104，1≤l≤r≤109。

输入样例：

9 27
3
1 5
10 11
9 11

输出样例：

3
-1
9

 

#include <iostream>  // 引入输入输出流库
#include <cstring>   // 引入字符串操作库
#include <algorithm> // 引入算法库（用于排序等）using namespace std; // 使用标准命名空间，避免每次调用标准库函数时加前缀std::const int N = 1350; // 定义常量N，表示数组q的最大容量int q[N], cnt; // 定义数组q用于存储公约数，cnt用于记录公约数的个数// 求最大公约数的递归函数
int gcd(int a, int b)
{return b ? gcd(b, a % b) : a; // 如果b不为0，则继续递归；否则返回a作为最大公约数
}// 初始化公约数的函数
void init_divisors(int a, int b)
{int d = gcd(a, b); // 计算a和b的最大公约数d// 遍历所有可能的公约数i，满足1 <= i <= sqrt(d)for (int i = 1; i <= d / i; i++) if (d % i == 0) // 如果d能被i整除，则i是公约数{q[cnt++] = i; // 将i加入数组q，并增加计数器cntif (i != d / i) q[cnt++] = d / i; // 如果i和d/i不同，也将d/i加入数组q}sort(q, q + cnt); // 对数组q中的公约数进行排序，确保后续查找时有序// 注意：暴力写法也需要排序。因为后面倒序枚举时找到第一个范围内的数，就直接输出了。// 只有排序后，才可以保证第一个找到的数是最大的数
}// 主函数
int main()
{int a, b;scanf("%d%d", &a, &b); // 输入两个整数a和binit_divisors(a, b); // 初始化a和b的所有公约数int n;scanf("%d", &n); // 输入查询次数nwhile (n--) // 循环处理n次查询{int L, R;scanf("%d%d", &L, &R); // 输入查询区间[L, R]bool found = false; // 标记是否找到符合条件的公约数for (int i = cnt - 1; i >= 0; i--) // 倒序遍历数组q中的公约数if (q[i] >= L && q[i] <= R) // 如果公约数q[i]在区间[L, R]内{printf("%d\n", q[i]); // 输出该公约数found = true; // 标记已找到break; // 跳出循环}if (!found) puts("-1"); // 如果未找到任何符合条件的公约数，输出-1}return 0; // 程序结束，返回0表示正常退出
}