当前位置: 首页 > news >正文

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

题目来源:

4199. 公约数 - AcWing题库

问题描述:

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

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

思路:

  • 找到 a a a, b b b两个数的最大公约数 g c = g c d ( a , b ) gc=gcd(a,b) gc=gcd(a,b)
  • 将此最大公约数的所有约数存放在一个数组 g g g
  • 二分查找该数组 g 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;
}
http://www.lryc.cn/news/334846.html

相关文章:

  • 【MySQL学习】MySQL的慢查询日志和错误日志
  • # C++之functional库用法整理
  • 查看MySQL版本的方式
  • k8s_入门_命令详解
  • 腾讯、阿里、字节….等大厂都更喜欢什么样的简历?
  • OpenHarmony实战:帆移植案例(中)
  • 武汉星起航:创始人张振邦智慧领航,孵化伙伴共绘跨境新蓝图!
  • 上下收缩、折叠面板
  • XC7A35T-2FGG484 嵌入式FPGA现场可编程门阵列 Xilinx
  • 淘宝订单API接口:电商业务自动化的新选择
  • 识典百科词条创建技巧,教你如何轻松创建热门识典百科词条!
  • iOS 开发中上传 IPA 文件的方法(无需 Mac 电脑)
  • 2024-04-08 问AI: 介绍一下AI 大神 吴恩达
  • Leetcode面试经典150_Q12整数转罗马数字
  • Docker-compose部署Alertmanager+Dingtalk+Prometheus+Grafana实现钉钉报警
  • 算法刷题记录 Day40
  • Android JNI基础
  • 裙边挡边带是什么
  • chabot项目介绍
  • ChromeOS 中自启动 Fcitx5 和托盘 stalonetray
  • 画图理解JVM相关内容
  • Scikit-Learn K均值聚类
  • 蓝桥杯 - 受伤的皇后
  • AcWing---乌龟棋---线性dp
  • python代码使用过程中使用快捷键注释时报错
  • go之web框架gin
  • SpringBoot 定时任务实践、定时任务按指定时间执行
  • MYSQL数据库故障排除与优化
  • 算法-数论-蓝桥杯
  • 222.完全二叉树节点个数