【洛谷 P1029】[NOIP2001 普及组] 最大公约数和最小公倍数问题 题解(辗转相除法)
[NOIP2001 普及组] 最大公约数和最小公倍数问题
题目描述
输入两个正整数 x 0 , y 0 x_0, y_0 x0,y0,求出满足下列条件的 P , Q P, Q P,Q 的个数:
-
P , Q P,Q P,Q 是正整数。
-
要求 P , Q P, Q P,Q 以 x 0 x_0 x0 为最大公约数,以 y 0 y_0 y0 为最小公倍数。
试求:满足条件的所有可能的 P , Q P, Q P,Q 的个数。
输入格式
一行两个正整数 x 0 , y 0 x_0, y_0 x0,y0。
输出格式
一行一个数,表示求出满足条件的 P , Q P, Q P,Q 的个数。
样例 #1
样例输入 #1
3 60
样例输出 #1
4
提示
P , Q P,Q P,Q 有 4 4 4 种:
- 3 , 60 3, 60 3,60。
- 15 , 12 15, 12 15,12。
- 12 , 15 12, 15 12,15。
- 60 , 3 60, 3 60,3。
对于 100 % 100\% 100% 的数据, 2 ≤ x 0 , y 0 ≤ 10 5 2 \le x_0, y_0 \le {10}^5 2≤x0,y0≤105。
【题目来源】
NOIP 2001 普及组第二题
思路
gcd(p, q) * lcm(p, q) = p * q
AC代码
#include <iostream>
#define AUTHOR "HEX9CF"
using namespace std;int gcd(int x, int y) {int r;if(x < y) {x ^= y ^= x ^= y;}r = x % y;if(!r) {return y;}return gcd(y, r);
}int main()
{int x, y;int cnt = 0;cin >> x >> y;for (int p = x; p <= y; p++){int q = x * y / p;int g = gcd(p, q);if (g == x && p * q / g == y){// cout << p << " " << q << endl;cnt++;}}cout << cnt << endl;return 0;
}
相关文章:
【洛谷 P1029】[NOIP2001 普及组] 最大公约数和最小公倍数问题 题解(辗转相除法)
[NOIP2001 普及组] 最大公约数和最小公倍数问题 题目描述 输入两个正整数 x 0 , y 0 x_0, y_0 x0,y0,求出满足下列条件的 P , Q P, Q P,Q 的个数: P , Q P,Q P,Q 是正整数。 要求 P , Q P, Q P,Q 以 x 0 x_0 x0 为最大公约数,以…...
Golang 中的 errors 包详解:返回自定义 error 类型
之前的文章《Golang 中的 errors 包详解》详细讲解了 errors 包的主要类型和函数,以及它们的使用方法。本文结合之前讲解的知识,来讲解一下根据自己或团队的项目要求如何返回自定义的 error 类型。 为什么需要自定义 error 类型? 在日常开发…...
C#开发的OpenRA游戏之信标按钮
前面已经分析了两个按钮:变卖和维修,接着下来就是分析信标按钮,这个按钮使用是比较少,但是对于多人游戏时,使用这个信号就很方便同盟军过来查看和帮助了,相当于一个朋友之间共同查看的地址。当你经过同盟标记的标志时,就会听到beacon detected,检测到信标,这就是你的盟…...
16字节协议的串口通信
1.协议要求 协议为帧传输,一共16字节。主要是2字节的固定帧头 EB 90,2字节的帧计数(用来计数发出的帧),10字节的数据和2字节的校验位 帧头:2字节,固定值 8’HEB、8’H90 帧计数:2字节,用来说明发出去帧是…...
升哲科技城市级“算力+数字底座”服务亮相2023服贸会
9月2日至6日,以“开放引领发展,合作共赢未来”为主题的2023年中国国际服务贸易交易会在北京隆重举办。作为城市级数据服务商,升哲科技(SENSORO)连续第四年参加服贸会,携城市级“算力数字底座”服务及在城市…...
动态规划之简单多状态
简单多状态 1. 按摩师(easy)2. 打家劫舍II (medium)3. 删除并获得点数(medium)4. 买卖股票的最佳时机含冷冻期(medium)5. 买卖股票的最佳时机III(hard) 1. 按…...
跨数据中心Multi-Fabric解决方案:L2和L3网络的高效连接和扩展
云数据中心里,为什么需要DCI互通? 云化数据中心,网络资源通过虚拟化技术形成资源池,实现业务与物理网络解耦,通过网络虚拟化,物理网络资源可以被分成多个虚拟网络资源,从而提高网络资源的使用效…...
upload-labs靶场通关详解
文章目录 Pass-01Pass-02Pass-03Pass-04Pass-05Pass-06Pass-07Pass-08Pass-09Pass-10Pass-11Pass-12Pass-13Pass-14Pass-15Pass-16Pass-17Pass-18Pass-19Pass-20方法一(文件夹名欺骗绕过)方法二(%00截断攻击) Pass-21 Pass-01 绕过…...
Leetcode刷题笔记--Hot41-50
1--二叉树的层序遍历(102) 主要思路: 经典广度优先搜索,基于队列; 对于本题需要将同一层的节点放在一个数组中,因此遍历的时候需要用一个变量 nums 来记录当前层的节点数,即 nums 等于队列元素的…...
「MySQL-02」数据库的操纵、备份、还原和编码规则
目录 一、库操作 1. 创建数据库 2. 查看所有数据库 3. 删除数据库 4. 修改数据库 5. 进入一个数据库 二、查看和设置数据库的编码规则 1. MySQL的两个编码规则:字符集和校验规则 2. 查看MySQL当前使用的字符集以及校验规则 3. 查看MySQL支持的所有字符集 4. 查看MyS…...
Effective C++条款24——若所有参数皆需类型转换,请为此采用non-member涵数(设计与声明)
我在导读中提过,令classes支持隐式类型转换通常是个糟糕的主意。当然这条规则有其例外,最常见的例外是在建立数值类型时。假设你设计一个class用来表现有理数,允许整数“隐式转换”为有理数似乎颇为合理。的确,它并不比C内置从int…...
决策工具箱:战略分析必备工具与框架
跟随时代的步伐,企业战略也在不断演化。无论是初创企业还是知名企业,都需要有效的战略工具来指导其业务发展。探索这些必备工具,并学习如何最大限度地利用它们,是企业的一个学习目标。 战略分析工具和框架有很多,其中…...
【压力测试指南】没有任何文档,小白也可以做的压力测试
前言 一般在执行压力测试之前,会由开发提供出接口文档,包含一些接口的详细参数,便于测试工程师编写测试脚本。但在某些情况下,接口等相关文档缺失,那作为Tester,我们该如何顺利的实施压力测试呢࿱…...
Linux: memory: memblock: debug
文章目录 代码memblock=debug实例log代码 将内存相关的一些日志打开: static int __init early_memblock(char *p) {if (p && strstr(p, "debug")...
搬家快递服务小程序的便利性
在当今快节奏的生活中,搬家可能是很多人都需要面对的问题。无论是新房子还是新办公室,都需要高效、便捷的搬家服务。本文将介绍如何使用第三方小程序制作平台,如乔拓云平台,开发一款高效便捷的搬家服务小程序。 1. 注册登录第三方…...
软件架构师 Debugging
软件架构师 Debugging 目录概述需求: 设计思路实现思路分析 参考资料和推荐阅读 Survive by day and develop by night. talk for import biz , show your perfect code,full busy,skip hardness,make a better result,wait for change,challenge Survi…...
7.1 项目1 学生通讯录管理:文本文件增删改查(C++版本)(自顶向下设计+断点调试) (A)
C自学精简教程 目录(必读) 作业目标: 这个作业中,你需要综合运用之前文章中的知识,来解决一个相对完整的应用程序。 作业描述: 1 在这个作业中你需要在文本文件中存储学生通讯录的信息,并在程序启动的时候加载这些…...
学习使用php判断阿里云oss图片单图或批量上传、查询图片文件是否存在
学习使用php判断阿里云oss图片单图或批量上传、查询图片文件是否存在 doesObjectExist doesObjectExist 主要函数doesObjectExist /*** Base64上传文件* param string|array $images* param string $model_path* param string $model_type* param string $upload_path* param…...
重磅| Falcon 180B 正式在 Hugging Face Hub 上发布!
引言 我们很高兴地宣布由 Technology Innovation Institute (TII) 训练的开源大模型 Falcon 180B 登陆 Hugging Face! Falcon 180B 为开源大模型树立了全新的标杆。作为当前最大的开源大模型,有180B 参数并且是在在 3.5 万亿 token 的 TII RefinedWeb 数…...
Linux命令行
目录 CLI GUI 命令行界面 图形界面 命令行提示符 # $ 编辑 命令一般由三个部分组成 历史命令,使用上下键,或者使用history,ctrlr搜索历史命令 通配符 *,? 切换用户 su 作业管理 &,jobs,bg,fg CLI GUI 命令行界面 …...
大话软工笔记—需求分析概述
需求分析,就是要对需求调研收集到的资料信息逐个地进行拆分、研究,从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要,后续设计的依据主要来自于需求分析的成果,包括: 项目的目的…...
Oracle查询表空间大小
1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...
linux 错误码总结
1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...
【决胜公务员考试】求职OMG——见面课测验1
2025最新版!!!6.8截至答题,大家注意呀! 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:( B ) A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...
WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)
一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解,适合用作学习或写简历项目背景说明。 🧠 一、概念简介:Solidity 合约开发 Solidity 是一种专门为 以太坊(Ethereum)平台编写智能合约的高级编…...
高防服务器能够抵御哪些网络攻击呢?
高防服务器作为一种有着高度防御能力的服务器,可以帮助网站应对分布式拒绝服务攻击,有效识别和清理一些恶意的网络流量,为用户提供安全且稳定的网络环境,那么,高防服务器一般都可以抵御哪些网络攻击呢?下面…...
在QWebEngineView上实现鼠标、触摸等事件捕获的解决方案
这个问题我看其他博主也写了,要么要会员、要么写的乱七八糟。这里我整理一下,把问题说清楚并且给出代码,拿去用就行,照着葫芦画瓢。 问题 在继承QWebEngineView后,重写mousePressEvent或event函数无法捕获鼠标按下事…...
VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP
编辑-虚拟网络编辑器-更改设置 选择桥接模式,然后找到相应的网卡(可以查看自己本机的网络连接) windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置,选择刚才配置的桥接模式 静态ip设置: 我用的ubuntu24桌…...
Git常用命令完全指南:从入门到精通
Git常用命令完全指南:从入门到精通 一、基础配置命令 1. 用户信息配置 # 设置全局用户名 git config --global user.name "你的名字"# 设置全局邮箱 git config --global user.email "你的邮箱example.com"# 查看所有配置 git config --list…...
Java求职者面试指南:Spring、Spring Boot、Spring MVC与MyBatis技术解析
Java求职者面试指南:Spring、Spring Boot、Spring MVC与MyBatis技术解析 一、第一轮基础概念问题 1. Spring框架的核心容器是什么?它的作用是什么? Spring框架的核心容器是IoC(控制反转)容器。它的主要作用是管理对…...
