【洛谷 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 命令行界面 …...
Flask RESTful 示例
目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题: 下面创建一个简单的Flask RESTful API示例。首先,我们需要创建环境,安装必要的依赖,然后…...
无法与IP建立连接,未能下载VSCode服务器
如题,在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈,发现是VSCode版本自动更新惹的祸!!! 在VSCode的帮助->关于这里发现前几天VSCode自动更新了,我的版本号变成了1.100.3 才导致了远程连接出…...
线程与协程
1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指:像函数调用/返回一样轻量地完成任务切换。 举例说明: 当你在程序中写一个函数调用: funcA() 然后 funcA 执行完后返回&…...
dedecms 织梦自定义表单留言增加ajax验证码功能
增加ajax功能模块,用户不点击提交按钮,只要输入框失去焦点,就会提前提示验证码是否正确。 一,模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...
STM32标准库-DMA直接存储器存取
文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA(Direct Memory Access)直接存储器存取 DMA可以提供外设…...
Python实现prophet 理论及参数优化
文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候,写过一篇简单实现,后期随着对该模型的深入研究,本次记录涉及到prophet 的公式以及参数调优,从公式可以更直观…...
基础测试工具使用经验
背景 vtune,perf, nsight system等基础测试工具,都是用过的,但是没有记录,都逐渐忘了。所以写这篇博客总结记录一下,只要以后发现新的用法,就记得来编辑补充一下 perf 比较基础的用法: 先改这…...
微信小程序云开发平台MySQL的连接方式
注:微信小程序云开发平台指的是腾讯云开发 先给结论:微信小程序云开发平台的MySQL,无法通过获取数据库连接信息的方式进行连接,连接只能通过云开发的SDK连接,具体要参考官方文档: 为什么? 因为…...
React---day11
14.4 react-redux第三方库 提供connect、thunk之类的函数 以获取一个banner数据为例子 store: 我们在使用异步的时候理应是要使用中间件的,但是configureStore 已经自动集成了 redux-thunk,注意action里面要返回函数 import { configureS…...
在Ubuntu24上采用Wine打开SourceInsight
1. 安装wine sudo apt install wine 2. 安装32位库支持,SourceInsight是32位程序 sudo dpkg --add-architecture i386 sudo apt update sudo apt install wine32:i386 3. 验证安装 wine --version 4. 安装必要的字体和库(解决显示问题) sudo apt install fonts-wqy…...
