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

【洛谷 P1029】[NOIP2001 普及组] 最大公约数和最小公倍数问题 题解(辗转相除法)

[NOIP2001 普及组] 最大公约数和最小公倍数问题

题目描述

输入两个正整数 x 0 , y 0 x_0, y_0 x0,y0,求出满足下列条件的 P , Q P, Q P,Q 的个数:

  1. P , Q P,Q P,Q 是正整数。

  2. 要求 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 种:

  1. 3 , 60 3, 60 3,60
  2. 15 , 12 15, 12 15,12
  3. 12 , 15 12, 15 12,15
  4. 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 2x0,y0105

【题目来源】

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​&#xff0c;求出满足下列条件的 P , Q P, Q P,Q 的个数&#xff1a; P , Q P,Q P,Q 是正整数。 要求 P , Q P, Q P,Q 以 x 0 x_0 x0​ 为最大公约数&#xff0c;以…...

Golang 中的 errors 包详解:返回自定义 error 类型

之前的文章《Golang 中的 errors 包详解》详细讲解了 errors 包的主要类型和函数&#xff0c;以及它们的使用方法。本文结合之前讲解的知识&#xff0c;来讲解一下根据自己或团队的项目要求如何返回自定义的 error 类型。 为什么需要自定义 error 类型&#xff1f; 在日常开发…...

C#开发的OpenRA游戏之信标按钮

前面已经分析了两个按钮:变卖和维修,接着下来就是分析信标按钮,这个按钮使用是比较少,但是对于多人游戏时,使用这个信号就很方便同盟军过来查看和帮助了,相当于一个朋友之间共同查看的地址。当你经过同盟标记的标志时,就会听到beacon detected,检测到信标,这就是你的盟…...

16字节协议的串口通信

1.协议要求 协议为帧传输&#xff0c;一共16字节。主要是2字节的固定帧头 EB 90&#xff0c;2字节的帧计数(用来计数发出的帧),10字节的数据和2字节的校验位 帧头&#xff1a;2字节&#xff0c;固定值 8’HEB、8’H90 帧计数&#xff1a;2字节&#xff0c;用来说明发出去帧是…...

升哲科技城市级“算力+数字底座”服务亮相2023服贸会

9月2日至6日&#xff0c;以“开放引领发展&#xff0c;合作共赢未来”为主题的2023年中国国际服务贸易交易会在北京隆重举办。作为城市级数据服务商&#xff0c;升哲科技&#xff08;SENSORO&#xff09;连续第四年参加服贸会&#xff0c;携城市级“算力数字底座”服务及在城市…...

动态规划之简单多状态

简单多状态 1. 按摩师&#xff08;easy&#xff09;2. 打家劫舍II &#xff08;medium&#xff09;3. 删除并获得点数&#xff08;medium&#xff09;4. 买卖股票的最佳时机含冷冻期&#xff08;medium&#xff09;5. 买卖股票的最佳时机III&#xff08;hard&#xff09; 1. 按…...

跨数据中心Multi-Fabric解决方案:L2和L3网络的高效连接和扩展

云数据中心里&#xff0c;为什么需要DCI互通&#xff1f; 云化数据中心&#xff0c;网络资源通过虚拟化技术形成资源池&#xff0c;实现业务与物理网络解耦&#xff0c;通过网络虚拟化&#xff0c;物理网络资源可以被分成多个虚拟网络资源&#xff0c;从而提高网络资源的使用效…...

upload-labs靶场通关详解

文章目录 Pass-01Pass-02Pass-03Pass-04Pass-05Pass-06Pass-07Pass-08Pass-09Pass-10Pass-11Pass-12Pass-13Pass-14Pass-15Pass-16Pass-17Pass-18Pass-19Pass-20方法一&#xff08;文件夹名欺骗绕过&#xff09;方法二&#xff08;%00截断攻击&#xff09; Pass-21 Pass-01 绕过…...

Leetcode刷题笔记--Hot41-50

1--二叉树的层序遍历&#xff08;102&#xff09; 主要思路&#xff1a; 经典广度优先搜索&#xff0c;基于队列&#xff1b; 对于本题需要将同一层的节点放在一个数组中&#xff0c;因此遍历的时候需要用一个变量 nums 来记录当前层的节点数&#xff0c;即 nums 等于队列元素的…...

「MySQL-02」数据库的操纵、备份、还原和编码规则

目录 一、库操作 1. 创建数据库 2. 查看所有数据库 3. 删除数据库 4. 修改数据库 5. 进入一个数据库 二、查看和设置数据库的编码规则 1. MySQL的两个编码规则&#xff1a;字符集和校验规则 2. 查看MySQL当前使用的字符集以及校验规则 3. 查看MySQL支持的所有字符集 4. 查看MyS…...

Effective C++条款24——若所有参数皆需类型转换,请为此采用non-member涵数(设计与声明)

我在导读中提过&#xff0c;令classes支持隐式类型转换通常是个糟糕的主意。当然这条规则有其例外&#xff0c;最常见的例外是在建立数值类型时。假设你设计一个class用来表现有理数&#xff0c;允许整数“隐式转换”为有理数似乎颇为合理。的确&#xff0c;它并不比C内置从int…...

决策工具箱:战略分析必备工具与框架

跟随时代的步伐&#xff0c;企业战略也在不断演化。无论是初创企业还是知名企业&#xff0c;都需要有效的战略工具来指导其业务发展。探索这些必备工具&#xff0c;并学习如何最大限度地利用它们&#xff0c;是企业的一个学习目标。 战略分析工具和框架有很多&#xff0c;其中…...

【压力测试指南】没有任何文档,小白也可以做的压力测试

前言 一般在执行压力测试之前&#xff0c;会由开发提供出接口文档&#xff0c;包含一些接口的详细参数&#xff0c;便于测试工程师编写测试脚本。但在某些情况下&#xff0c;接口等相关文档缺失&#xff0c;那作为Tester&#xff0c;我们该如何顺利的实施压力测试呢&#xff1…...

Linux: memory: memblock: debug

文章目录 代码memblock=debug实例log代码 将内存相关的一些日志打开: static int __init early_memblock(char *p) {if (p && strstr(p, "debug")...

搬家快递服务小程序的便利性

在当今快节奏的生活中&#xff0c;搬家可能是很多人都需要面对的问题。无论是新房子还是新办公室&#xff0c;都需要高效、便捷的搬家服务。本文将介绍如何使用第三方小程序制作平台&#xff0c;如乔拓云平台&#xff0c;开发一款高效便捷的搬家服务小程序。 1. 注册登录第三方…...

软件架构师 Debugging

软件架构师 Debugging 目录概述需求&#xff1a; 设计思路实现思路分析 参考资料和推荐阅读 Survive by day and develop by night. talk for import biz , show your perfect code,full busy&#xff0c;skip hardness,make a better result,wait for change,challenge Survi…...

​7.1 项目1 学生通讯录管理:文本文件增删改查(C++版本)(自顶向下设计+断点调试) (A)​

C自学精简教程 目录(必读) 作业目标&#xff1a; 这个作业中&#xff0c;你需要综合运用之前文章中的知识&#xff0c;来解决一个相对完整的应用程序。 作业描述&#xff1a; 1 在这个作业中你需要在文本文件中存储学生通讯录的信息&#xff0c;并在程序启动的时候加载这些…...

学习使用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&#xff01; Falcon 180B 为开源大模型树立了全新的标杆。作为当前最大的开源大模型&#xff0c;有180B 参数并且是在在 3.5 万亿 token 的 TII RefinedWeb 数…...

Linux命令行

目录 CLI GUI 命令行界面 图形界面 命令行提示符 # $ ​编辑 命令一般由三个部分组成 历史命令&#xff0c;使用上下键&#xff0c;或者使用history&#xff0c;ctrlr搜索历史命令 通配符 *,? 切换用户 su 作业管理 &&#xff0c;jobs,bg,fg CLI GUI 命令行界面 …...

Wireshark抓Android包,选对网卡是关键!教你一眼识别哪个是手机流量(附避坑指南)

Wireshark抓取Android流量的精准定位指南 在移动应用开发、网络调试或安全分析过程中&#xff0c;经常需要抓取Android设备的网络流量进行分析。Wireshark作为业界标准的网络协议分析工具&#xff0c;能够帮助我们深入理解数据流动的细节。然而&#xff0c;当电脑连接了多个网络…...

WDMHDA:Windows 旧系统高清音频驱动的突破与挑战

【导语&#xff1a;WDMHDA 是一款适用于 Windows 98SE / ME 的高清音频驱动程序&#xff0c;为旧系统的音频功能带来新可能。但目前处于 Alpha 阶段&#xff0c;存在诸多待解决问题&#xff0c;其发展对旧系统音频生态有重要影响。】WDMHDA&#xff1a;旧系统音频驱动新选择WDM…...

Qwen3-ForcedAligner-0.6B低延迟实时处理能力展示

Qwen3-ForcedAligner-0.6B低延迟实时处理能力展示 如果你正在寻找一个能快速、精准地为语音和文字“打上时间标签”的工具&#xff0c;那么Qwen3-ForcedAligner-0.6B绝对值得你花几分钟了解一下。想象一下&#xff0c;一段长达5分钟的演讲音频&#xff0c;你需要精确知道每个词…...

3大维度解析BGE向量技术:从原理到检索增强实践

3大维度解析BGE向量技术&#xff1a;从原理到检索增强实践 【免费下载链接】FlagEmbedding Dense Retrieval and Retrieval-augmented LLMs 项目地址: https://gitcode.com/GitHub_Trending/fl/FlagEmbedding 文本嵌入技术是现代AI系统的核心组件&#xff0c;而检索增强…...

2026最新大模型应用开发学习路线(附时间规划,小白/程序员必收藏)

一、先破局&#xff1a;初学者必看&#xff01;Python 还是 Java 选对不踩坑 很多小白和入门程序员&#xff0c;刚接触大模型开发就卡在编程语言选择上&#xff0c;浪费大量时间纠结。不绕弯子&#xff0c;直接给结论&#xff0c;结合AI开发场景帮你精准选择&#xff0c;新手直…...

CST中利用SPICE语言自定义复杂lumped element电路的实战指南

1. 突破CST自带元件的限制&#xff1a;为什么需要SPICE语言 刚开始用CST做电路仿真时&#xff0c;我也觉得自带的RLC元件够用了——直到遇到一个带滤波功能的耦合器项目。当时需要模拟一个包含寄生参数的复杂匹配网络&#xff0c;自带的并联RLC元件死活调不出理想的频响曲线。这…...

Rockchip Android 12编译踩坑记:手把手教你修改BoardConfig.mk生成userdata.img

Rockchip Android 12编译实战&#xff1a;从BoardConfig.mk修改到userdata.img生成的避坑指南 第一次在Rockchip平台上编译Android 12系统时&#xff0c;我遇到了一个令人抓狂的问题——编译过程看似顺利&#xff0c;但生成的固件烧写到设备后&#xff0c;系统始终无法正常启动…...

ATOM-PRINTER嵌入式热敏打印固件深度解析

1. ATOM-PRINTER 嵌入式打印库深度解析与工程实践指南ATOM-PRINTER 是 M5Stack 推出的面向 ESP32 平台的轻量级嵌入式热敏打印固件库&#xff0c;专为 M5Stack Atom 系列微型主控模块&#xff08;搭载 ESP32-WROVER-B&#xff09;设计。该库并非传统意义上的“驱动层”C/C 库&a…...

【开题答辩全过程】以 基于JSP框架的医疗管理系统为例,包含答辩的问题和答案

个人简介一名14年经验的资深毕设内行人&#xff0c;语言擅长Java、php、微信小程序、Python、Golang、安卓Android等开发项目包括大数据、深度学习、网站、小程序、安卓、算法。平常会做一些项目定制化开发、代码讲解、答辩教学、文档编写、也懂一些降重方面的技巧。感谢大家的…...

Leather Dress Collection 模型Java后端集成指南:SpringBoot微服务开发

Leather Dress Collection 模型Java后端集成指南&#xff1a;SpringBoot微服务开发 最近在做一个电商相关的项目&#xff0c;需要集成一个能生成皮革服饰设计图的AI模型&#xff0c;正好接触到了Leather Dress Collection。作为后端开发&#xff0c;我的第一反应就是&#xff…...