【codevs1012】最大公约数和最小公倍数
2024-10-19 00:22:45
题目描述 Description
输入二个正整数x0,y0(2<=x0<100000,2<=y0<=1000000),求出满足下列条件的P,Q的个数
条件: 1.P,Q是正整数
2.要求P,Q以x0为最大公约数,以y0为最小公倍数.
试求:满足条件的所有可能的两个正整数的个数.
输入描述 Input Description
二个正整数x0,y0
输出描述 Output Description
满足条件的所有可能的两个正整数的个数
样例输入 Sample Input
3 60
样例输出 Sample Output
4
分析:
p和q的最大公约数(gcd)是x,最小公倍数(lcm)是y
那么p*q=x*y
设p=x*i,q=x*j,i和j互质
则p*q=(x*i)*(x*j)=x*y,那就有i*j=y/x
我们可以枚举i,从i=1开始,直到i*i>y/x
如果i是y/x的因子
然后j=(y/x)/i
再判断i和j是否互质
因为每次得到的两个数中比较小的就是i,比较大的数是j,i是小于根号(y/x)的,j就是大于根号(y/x)因此不会重复计算,那算到一次,答案就累加2。
代码:
#include<iostream>
using namespace std; int gcd(int x,int y)
{
return(x%y==?y:gcd(y,x%y));
}
int main()
{
int x,y,ans=;
cin>>x>>y;
if(y%x){
cout<<;
return ;
}
y=y/x;
for(int i=; i*i<=y; i++)
{
if(y%i==&&gcd(i,y/i)==)
ans+=;
}
cout<<ans<<endl;
}
最新文章
- jQuery可拖拽3D万花筒旋转特效
- React Native知识3-TextInput组件
- MicroERP开发技术分享:技术选型
- 字符串截取函数-c语言
- CI控制器中设置在其它方法中可用的变量
- CKEDITOR使用与配置
- 进击的java - tomcat的安装,配置都正确之后,还是报错
- C# rmi例子
- nopCommerce 数据库初试化及数据操作
- yum的一些用法
- Sublime Text 3 若干问题解决办法
- Delphi 技巧改造HINT的输出方式
- java静态初始化代码块
- redis的两种安装方法
- C#中DataTable与XML格式的相互转换
- vim 基础命令大全
- 用十条命令在一分钟内检查 Linux 服务器性能
- CA证书扫盲,https讲解
- 设置JAVA HOME环境变量的秕处理
- 卖座网一处SQL注射(Http Referer sqlinjection)
热门文章
- javascript获取元素的方法[xyyit]
- JVM监测&;工具[转]
- smarty foreach循环
- MySQL Index详解
- Cordova - 使用Cordova开发iOS应用实战1(配置、开发第一个应用)
- mysql 控制台上传数据库
- 进程控制块(Process Control Block, PCB)
- ORACLE查出表所有的触发器及触发器详细信息
- Effective java 第2版 - 笔记(01) 单例(Singleton)的枚举(enum)实现
- 【转】如何拿到半数面试公司Offer——我的Python求职之路