义乌哪里做网站好,连云港建设部网站,景观设计公司利润,网站如何做中英文切换4199.公约数
4199. 公约数 - AcWing题库难度#xff1a;中等时/空限制#xff1a;1s / 256MB总通过数#xff1a;2801总尝试数#xff1a;7059来源#xff1a;AcWing第30场周赛算法标签最大公约数试除法二分 题目内容
给定两个正整数 a 和 b。 你需要回答 q 个询问。 每…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≤1001≤q≤20。 所有测试点满足 1≤a,b≤1091≤q≤1041≤l≤r≤10^9。
输入样例
9 27
3
1 5
10 11
9 11输出样例
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一定可以唯一分解成若干的质因子相乘的结果 a P 1 a 1 P 2 a 2 … P k a k b P 1 b 1 P 2 b 2 … P k b k ( a , b ) P 1 m i n ( a 1 , b 1 ) P 2 m i n ( a 2 , b 2 ) … P k m i n ( a k , b k ) \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} aP1a1P2a2…PkakbP1b1P2b2…Pkbk(a,b)P1min(a1,b1)P2min(a2,b2)…Pkmin(ak,bk) 如果x既可以整除a也可以整除b的话 就一定意味着 x P 1 x 1 P 2 x 2 … P k x k x P_{1}^{x_{1}}P_{2}^{x_{2}}\dots P_{k}^{x_{k}} xP1x1P2x2…Pkxk 并且 x i ≤ a i x i ≤ b i x_{i} \le a_{i} \qquad x_{i} \le b_{i} xi≤aixi≤bi 因此 x i ≤ m i n ( a i , b i ) x_{i} \le min(a_{i},b_{i}) xi≤min(ai,bi) 所以x一定是a和b的最大公约数的约数 直接可以先求出a和b的最大公约数等于d x可以取值的范围就是d的所有约数 一个数的所有约数最多就是根号n级别 所以可以先将d的所有约数找出来放到一个数组里排个序
接下来要找到l到r之间的最大的一个数
可以二分一下 在所有约数里边二分出来小于等于r的最大数 判断一下这个数是不是在l到r之间就可以了
求一个数的所有约数
代码
#include iostream
#include cstring
#include algorithm
#include vectorusing namespace std;//最大公约数模板
int gcd (int a, int b) //欧几里得算法
{return b ? gcd(b, a % b) : a;
}//用试除法求所有约数返回到vector里
vectorint get_divisors(int x)
{//定义一个vector用来存所有的约数vectorint 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;
}
