当前位置: 首页 > 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 命令行界面 …...

RTX 3060用户必看:解决nvcc报错‘Unsupported gpu architecture‘的完整指南

RTX 3060显卡CUDA开发实战&#xff1a;彻底解决Unsupported gpu architecture编译错误 当你兴奋地拆开新入手的RTX 3060显卡准备大展拳脚时&#xff0c;却在编译CUDA项目时遭遇了令人沮丧的Unsupported gpu architecture错误。这个看似简单的报错背后&#xff0c;隐藏着CUDA开…...

InnoDB 事务 undo log 与 MVCC 可视化讲解(画流程图+伪代码)

InnoDB 事务 undo log 与 MVCC 可视化讲解(画流程图+伪代码) 前言 在MySQL的InnoDB存储引擎中,事务的四大特性(ACID)是其核心能力之一。其中,隔离性(Isolation)和一致性(Consistency)的实现离不开undo log与MVCC(多版本并发控制)的精妙设计。 本文将从底层原理出…...

OpenClaw多模型对比:ollama-QwQ-32B与云端API在自动化任务中的表现

OpenClaw多模型对比&#xff1a;ollama-QwQ-32B与云端API在自动化任务中的表现 1. 测试背景与实验设计 去年冬天&#xff0c;当我第一次尝试用OpenClaw自动化处理堆积如月的合同文件时&#xff0c;面对本地部署和云端API两种选择&#xff0c;陷入了典型的"技术选择困难症…...

NSudo终极指南:3大核心功能解锁Windows系统权限管理新境界

NSudo终极指南&#xff1a;3大核心功能解锁Windows系统权限管理新境界 【免费下载链接】NSudo [Deprecated, work in progress alternative: https://github.com/M2Team/NanaRun] Series of System Administration Tools 项目地址: https://gitcode.com/gh_mirrors/ns/NSudo …...

Django CORS Headers 终极指南:10个企业级跨域架构设计技巧

Django CORS Headers 终极指南&#xff1a;10个企业级跨域架构设计技巧 【免费下载链接】django-cors-headers Django app for handling the server headers required for Cross-Origin Resource Sharing (CORS) 项目地址: https://gitcode.com/gh_mirrors/dj/django-cors-he…...

Ubuntu 20.04 下通过 PPA 快速部署 qBittorrent 及配置指南

1. 为什么选择qBittorrent&#xff1f; 如果你经常需要下载大型文件&#xff0c;比如开源系统镜像、影视素材或者游戏资源&#xff0c;那么一个靠谱的BT客户端绝对是刚需。我在Ubuntu上试过各种BT工具&#xff0c;最终发现qBittorrent是最稳定高效的选择。它完全开源免费&#…...

二手破损手机涨价,业余 NAS 玩家如何破局?

最近打开手机回收 App&#xff0c;发现家里那台屏幕碎成渣、开不了机的旧安卓机&#xff0c;居然能卖一百多&#xff0c;甚至两三百。你可能会想&#xff1a;这是天上掉馅饼&#xff0c;还是 NAS 玩家的“矿难”前兆&#xff1f; 作为一名业余 NAS 玩家&#xff0c;我正好踩在这…...

三相永磁同步电机FOC控制实战:从霍尔传感器配置到SVPWM调参避坑指南

三相永磁同步电机FOC控制实战&#xff1a;从霍尔传感器配置到SVPWM调参避坑指南 当你在深夜的实验室里盯着示波器上跳动的波形&#xff0c;试图让一台三相永磁同步电机平稳启动时&#xff0c;是否经历过这样的场景&#xff1a;明明按照手册配置了所有参数&#xff0c;电机却像喝…...

PDF-Parser-1.0保姆级教程:5分钟搞定PDF文档智能解析,小白也能快速上手

PDF-Parser-1.0保姆级教程&#xff1a;5分钟搞定PDF文档智能解析&#xff0c;小白也能快速上手 1. 为什么选择PDF-Parser-1.0&#xff1f; 你是否遇到过这些烦恼&#xff1a; 从PDF复制文字到Word后格式全乱表格数据粘贴后变成一堆乱码论文里的数学公式无法编辑双栏排版的文…...

实时手机检测-通用实战案例:手机质检报告自动生成系统集成方案

实时手机检测-通用实战案例&#xff1a;手机质检报告自动生成系统集成方案 1. 引言&#xff1a;从人工质检到智能报告的跨越 想象一下&#xff0c;在一个大型手机生产线上&#xff0c;质检员每天需要手动检查成千上万张手机外观照片&#xff0c;寻找划痕、污渍、装配瑕疵。这…...