【AcWing】蓝桥杯集训每日一题Day25|最大公约数|算数基本定理|4199.公约数(C++)

本文主要是介绍【AcWing】蓝桥杯集训每日一题Day25|最大公约数|算数基本定理|4199.公约数(C++)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

4199.公约数

4199. 公约数 - AcWing题库
难度：中等
时/空限制：1s / 256MB
总通过数：2801
总尝试数：7059
来源： AcWing第30场周赛
算法标签最大公约数试除法二分

题目内容

给定两个正整数 a 和 b。
你需要回答 q 个询问。
每个询问给定两个整数 l,r，你需要找到最大的整数 x，满足：

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

输入格式

第一行包含两个整数 a,b。
第二行包含一个整数 q。
接下来 q 行，每行包含两个整数 l,r。

输出格式

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

数据范围

前六个测试点满足 1≤a,b≤100，1≤q≤20。
所有测试点满足 1≤a,b≤10^{9，1≤q≤10}4，1≤l≤r≤10^9。

输入样例：

输出样例：

3
-1
9

题目解析

给两个正整数，每次找a和b在l到r之间的公约数

a和b都是10^9
测试数量是1万

如果x是a和b的约数的话
那么x一定是a和b的最大公约数的约数

证明

如果x可以整除a，并且x可以整除b的话，那么x就一定可以整除a和b的最大公约数

反过来说
a和b的最大公约数里的任何一个约数，都一定既是a的约数也是b的约数
如果一个数是a和b的最大公约数的约数，这个数就既是a的约数也是b的约数

要证明一件事，x所有可以选择的集合，就是a和b的最大公约数的约数
证明两个集合是一一对应的，要证明右边任取一个元素一定属于左边
任取一个a和b的最大公约数的约数，一定既能整除a也能整除b，所以属于左边

还要反过来证明左边任取一个元素一定属于右边
任取一个既是a的约数也是b的约数的数，一定要证明出来是a和b的最大公约数的约数

用算数基本定理
a一定可以唯一分解成若干的质因子相乘的结果
$\begin{array}{} \\ a = P_{1}^{a_{1}}P_{2}^{a_{2}}\dots P_{k}^{a_{k}} \\ b = P_{1}^{b_{1}}P_{2}^{b_{2}}\dots P_{k}^{b_{k}} \\ (a,b)=P_{1}^{min(a_{1},b_{1})}P_{2}^{min(a_{2},b_{2})}\dots P_{k}^{min(a_{k},b_{k})} \end{array}$
如果x既可以整除a，也可以整除b的话
就一定意味着
$P_{1}^{x_{1}}P_{2}^{x_{2}}\dots P_{k}^{x_{k}}$
并且
$x_{i} \le a_{i} \qquad x_{i} \le b_{i}$
因此
$x_{i} \le min(a_{i},b_{i})$
所以x一定是a和b的最大公约数的约数

直接可以先求出a和b的最大公约数，等于d
x可以取值的范围就是d的所有约数
一个数的所有约数最多就是根号n级别
所以可以先将d的所有约数找出来，放到一个数组里排个序

接下来要找到l到r之间的最大的一个数

可以二分一下
在所有约数里边，二分出来小于等于r的最大数
判断一下这个数是不是在l到r之间就可以了

求一个数的所有约数

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>using namespace std;//最大公约数模板
int gcd (int a, int b)  //欧几里得算法
{return b ? gcd(b, a % b) : a;
}//用试除法求所有约数，返回到vector里
vector<int> get_divisors(int x)
{//定义一个vector用来存所有的约数vector<int> res;for (int i = 1; i <= x / i; i ++)if (x % i == 0){res.push_back(i);if (i != x / i) res.push_back(x / i);}sort(res.begin(), res.end());return res;
}int main()
{//读入a和b，求最大公约数int a, b;scanf("%d%d", &a, &b);int d = gcd(a, b);//求a和b的所有约数auto ds = get_divisors(d);//读入询问的数量int q;scanf("%d", &q);//依次读入每个询问while (q --){int L, R;scanf("%d%d", &L, &R);//二分int l = 0, r = ds.size() - 1;while (l < r){int mid = l + r + 1 >> 1; //上取整if (ds[mid] <= R) //二分要在mid或mid的右边l = mid;else r = mid - 1;} int x = ds[r];if (x >= L && x <= R) printf("%d\n", x);else puts("-1");}return 0;
}

这篇关于【AcWing】蓝桥杯集训每日一题Day25|最大公约数|算数基本定理|4199.公约数(C++)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！