当前位置: 首页 > 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;
}
http://www.lryc.cn/news/156583.html

相关文章:

  • Golang 中的 errors 包详解:返回自定义 error 类型
  • C#开发的OpenRA游戏之信标按钮
  • 16字节协议的串口通信
  • 升哲科技城市级“算力+数字底座”服务亮相2023服贸会
  • 动态规划之简单多状态
  • 跨数据中心Multi-Fabric解决方案:L2和L3网络的高效连接和扩展
  • upload-labs靶场通关详解
  • Leetcode刷题笔记--Hot41-50
  • 「MySQL-02」数据库的操纵、备份、还原和编码规则
  • Effective C++条款24——若所有参数皆需类型转换,请为此采用non-member涵数(设计与声明)
  • 决策工具箱:战略分析必备工具与框架
  • 【压力测试指南】没有任何文档,小白也可以做的压力测试
  • Linux: memory: memblock: debug
  • 搬家快递服务小程序的便利性
  • 软件架构师 Debugging
  • ​7.1 项目1 学生通讯录管理:文本文件增删改查(C++版本)(自顶向下设计+断点调试) (A)​
  • 学习使用php判断阿里云oss图片单图或批量上传、查询图片文件是否存在
  • 重磅| Falcon 180B 正式在 Hugging Face Hub 上发布!
  • Linux命令行
  • [持续更新]计算机经典面试题基础篇Day1
  • ProcessWindowFunction 结合自定义触发器的陷阱
  • 什么是jvm
  • kettle通过java步骤获取汉字首拼
  • Conformer: Local Features Coupling Global Representationsfor Visual Recognition
  • java8-Stream流常用API
  • React 任务调度
  • 小白开始学习C++
  • SpringMVC入门的注解、参数传递、返回值和页面跳转---超详细教学
  • 【复习socket】每天40min,我们一起用70天稳扎稳打学完《JavaEE初阶》——28/70 第二十八天
  • vue2踩坑之项目:生成二维码使用vue-print-nb打印二维码