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

2024-03-05 20:08

本文主要是介绍NOIP2001普及组 最大公约数和最小公倍数问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

最大公约数和最小公倍数问题


http://218.5.5.242:9018/JudgeOnline/problem.php?id=1111

时间限制: 1 Sec  

内存限制: 128 MB

题目描述


  输入二个正整数x0,y0(2<=x0<100000,2<=y0<=1000000),求出满足下列条件的P,Q的个数。
  条件:  
  1、P,Q是正整数
  2、要求P,Q以x0为最大公约数,以y0为最小公倍数。
  试求:满足条件的所有可能的两个正整数的个数。


   样例
  输入:x0=3   yo=60
  输出:4


  说明(不用输出)此时的  P  Q  分别为: 
     3   60
  15   12
  12   15
  60    3
  所以:满足条件的所有可能的两个正整数的个数共4种.


输入
输入只有一行,为两个正整数x0和y0。

输出
输出只有一行,为满足条件的所有可能的两个正整数的个数。

样例输入
3 60
样例输出
4
来源
NOIP2001普及组


此题较UVa 10892(点击打开题解)更为简单。


完整代码:

/*0ms,964KB*/#include<cstdio>int main()
{long long m, n, nn, ans, i, count;scanf("%lld%lld", &m, &n);if (n % m) putchar('0');///注意特判else{n /= m;ans = 1;for (i = 2; i * i <= n; i += 2)///不用求素数,因为范围很小(注意n在不断减小){if (n % i == 0){count = 0;while (n % i == 0){n /= i;++count;}ans <<= 1;}if (i == 2)--i;///小技巧}if (n > 1) ans <<= 1;printf("%lld", ans);}return 0;
}

这篇关于NOIP2001普及组 最大公约数和最小公倍数问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/777666

相关文章

mybatis和mybatis-plus设置值为null不起作用问题及解决

《mybatis和mybatis-plus设置值为null不起作用问题及解决》Mybatis-Plus的FieldStrategy主要用于控制新增、更新和查询时对空值的处理策略,通过配置不同的策略类型... 目录MyBATis-plusFieldStrategy作用FieldStrategy类型每种策略的作

linux下多个硬盘划分到同一挂载点问题

《linux下多个硬盘划分到同一挂载点问题》在Linux系统中,将多个硬盘划分到同一挂载点需要通过逻辑卷管理(LVM)来实现,首先,需要将物理存储设备(如硬盘分区)创建为物理卷,然后,将这些物理卷组成... 目录linux下多个硬盘划分到同一挂载点需要明确的几个概念硬盘插上默认的是非lvm总结Linux下多

Python Jupyter Notebook导包报错问题及解决

《PythonJupyterNotebook导包报错问题及解决》在conda环境中安装包后,JupyterNotebook导入时出现ImportError,可能是由于包版本不对应或版本太高,解决方... 目录问题解决方法重新安装Jupyter NoteBook 更改Kernel总结问题在conda上安装了

pip install jupyterlab失败的原因问题及探索

《pipinstalljupyterlab失败的原因问题及探索》在学习Yolo模型时,尝试安装JupyterLab但遇到错误,错误提示缺少Rust和Cargo编译环境,因为pywinpty包需要它... 目录背景问题解决方案总结背景最近在学习Yolo模型,然后其中要下载jupyter(有点LSVmu像一个

解决jupyterLab打开后出现Config option `template_path`not recognized by `ExporterCollapsibleHeadings`问题

《解决jupyterLab打开后出现Configoption`template_path`notrecognizedby`ExporterCollapsibleHeadings`问题》在Ju... 目录jupyterLab打开后出现“templandroidate_path”相关问题这是 tensorflo

如何解决Pycharm编辑内容时有光标的问题

《如何解决Pycharm编辑内容时有光标的问题》文章介绍了如何在PyCharm中配置VimEmulator插件,包括检查插件是否已安装、下载插件以及安装IdeaVim插件的步骤... 目录Pycharm编辑内容时有光标1.如果Vim Emulator前面有对勾2.www.chinasem.cn如果tools工

最长公共子序列问题的深度分析与Java实现方式

《最长公共子序列问题的深度分析与Java实现方式》本文详细介绍了最长公共子序列(LCS)问题,包括其概念、暴力解法、动态规划解法,并提供了Java代码实现,暴力解法虽然简单,但在大数据处理中效率较低,... 目录最长公共子序列问题概述问题理解与示例分析暴力解法思路与示例代码动态规划解法DP 表的构建与意义动

Java多线程父线程向子线程传值问题及解决

《Java多线程父线程向子线程传值问题及解决》文章总结了5种解决父子之间数据传递困扰的解决方案,包括ThreadLocal+TaskDecorator、UserUtils、CustomTaskDeco... 目录1 背景2 ThreadLocal+TaskDecorator3 RequestContextH

关于Spring @Bean 相同加载顺序不同结果不同的问题记录

《关于Spring@Bean相同加载顺序不同结果不同的问题记录》本文主要探讨了在Spring5.1.3.RELEASE版本下,当有两个全注解类定义相同类型的Bean时,由于加载顺序不同,最终生成的... 目录问题说明测试输出1测试输出2@Bean注解的BeanDefiChina编程nition加入时机总结问题说明

关于最长递增子序列问题概述

《关于最长递增子序列问题概述》本文详细介绍了最长递增子序列问题的定义及两种优化解法:贪心+二分查找和动态规划+状态压缩,贪心+二分查找时间复杂度为O(nlogn),通过维护一个有序的“尾巴”数组来高效... 一、最长递增子序列问题概述1. 问题定义给定一个整数序列,例如 nums = [10, 9, 2