北京个人网站开发制作,网站空间那个好,上海 网站设计公司,电商公司做网站题目描述#xff1a;
给定两个正整数 a 和 b。
你需要回答 q 个询问。
每个询问给定两个整数 l,r#xff0c;你需要找到最大的整数 x#xff0c;满足#xff1a;
x 是 a和 b 的公约数。l≤x≤r。
输入格式
第一行包含两个整数 a,b。
第二行包含一个整数 q。
接下来…题目描述
给定两个正整数 a 和 b。
你需要回答 q 个询问。
每个询问给定两个整数 l,r你需要找到最大的整数 x满足
x 是 a和 b 的公约数。l≤x≤r。
输入格式
第一行包含两个整数 a,b。
第二行包含一个整数 q。
接下来 q 行每行包含两个整数 l,r。
输出格式
每个询问输出一行答案即满足条件的最大的 x如果询问无解则输出 −1−1。
数据范围
前六个测试点满足 1≤a,b≤1001≤q≤20。 所有测试点满足 1≤a,b≤10^91≤q≤10^41≤l≤r≤10^9。
输入样例
9 27
3
1 5
10 11
9 11输出样例
3
-1
9 解题思路:
设d为a,b的最大公约数x为d所有约数p为质约数 有图可知 a,b质约数和x相同x为d的约数,因此求出d的所以有约数再排序找出l-r的最大值即可.
参考代码
###暴力#include iostream
#include cstring
#include algorithmusing namespace std;
const int N 1350;
int p[N];
int a,b,cnt;int gcd(int a,int b)
{return b ? gcd(b,a%b) : a;
}void solve(int a,int b)
{int d gcd(a,b);for(int i1;id/i;i){if(d%i0){p[cnt] i;if(i!d/i) p[cnt] d/i;}}sort(p,pcnt);
}int main()
{scanf(%d%d, a, b);solve(a,b);int n;cinn;while (n -- ){int l,r;cinlr;bool st false;for(int icnt-1;i0;i--){if(p[i]l p[i]r){printf(%d\n,p[i]);st true;break;}}if(!st) puts(-1);}return 0;
}###二分#include iostream
#include cstring
#include algorithm
#include vectorusing namespace std;
const int N 1350;
int p[N];
int a,b,cnt;int gcd(int a,int b)
{return b ? gcd(b,a%b) : a;
}void solve(int a,int b)
{int d gcd(a,b);for(int i1;id/i;i){if(d%i0){p[cnt] i;if(i!d/i) p[cnt] d/i;}}sort(p,pcnt);
}int main()
{scanf(%d%d, a, b);solve(a,b);int n;cinn;while (n -- ){int l,r;cinlr;int L 0,R cnt - 1;while(LR){int mid L R 1 1;if(p[mid]r) L mid;else R mid - 1;}if(p[L]l) printf(%d\n,p[L]);else puts(-1);}return 0;
}
