蓝桥集训之公约数

本文主要是介绍蓝桥集训之公约数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

蓝桥集训之公约数

• 核心思想： 最大公约数gcd+二分

  • 数学性质ab的约数一定是ab最大公约数的约数
    • 给定ab先求出二者最大公约数d
  • 然后求出d的所有约数
  • 再根据给定LR求出所求约数的位置

•   #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<int> get_divide(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(){int a,b;cin>>a>>b;int d = gcd(a,b);auto ds = get_divide(d);int T;cin>>T;while(T--){int L,R;cin>>L>>R;int l=0,r=ds.size()-1;while(l<r){int mid = l+r+1>>1;if(ds[mid] <= R) l = mid;else r = mid-1;}int x = ds[r];  //最终求出的约数if(x>=L && x<=R) cout<<x<<endl;else cout<<"-1"<<endl;}return 0;}
  

这篇关于蓝桥集训之公约数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---