【蓝桥杯每日一题】4.8 公约数

题目来源：

4199. 公约数 - AcWing题库

问题描述：

​ 找到最大整数x，需满足下面两个条件

• $x$是$a$,$b$的公约数
• $l<=x<=r$

思路：

• 找到$a$,$b$两个数的最大公约数$gc=gcd(a,b)$
• 将此最大公约数的所有约数存放在一个数组$g$中
• 二分查找该数组$g$，找到满足条件的值

AC Code:

//gcd+约数分解+二分查找
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10; //x的约数不会超过2*sqrt(x)个ll a,b,q,x,y;
ll g[N];
ll cnt=0;int gcd(ll a,ll b)
{return b?gcd(b,a%b):a;
}void div(ll x)
{for(ll i=1;i<=x/i;i++){if(x%i==0){g[cnt++]=i;if(i!=x/i) g[cnt++] = x/i; //相当于用遍历从1->x的时间 记录了x的所有约数}	}sort(g,g+cnt);
}
int main()
{scanf("%ld%ld",&a,&b);div(gcd(a,b));scanf("%ld",&q);while(q--){scanf("%ld%ld",&x,&y);int l=-1,r=cnt;while(l+1<r){int mid=(l+r)/2;if(g[mid]<=y) l=mid;else r=mid;}if(g[l]>=x) printf("%ld\n",g[l]);else printf("-1\n");}return 0;
}