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

题目描述

输入二个正整数x0,y0(2<=x0<100000,2<=y0<=1000000),求出满足下列条件的P,Q的个数

条件:

1.P,Q是正整数

2.要求P,Q以x0为最大公约数,以y0为最小公倍数.

试求:满足条件的所有可能的两个正整数的个数.

输入输出格式

输入格式:

二个正整数x0,y0

输出格式:

一个数,表示求出满足条件的P,Q的个数

输入输出样例

输入样例#1:

3 60
输出样例#1:

4

说明

P,Q有4种

3 60 15 12 12 15 60 3

本题一个比较重要的等式:a * b / gcd(a, b) = lcm(a, b)

尤次,仅需枚举a,可求得b,然后判断gcd(a, b)是否为x0,同时由于精度问题,还应考虑求的b是否正确

a的枚举:仅需枚举x0的倍数即可,同时应该小于等于y0的两倍,十分显然,

#include <bits/stdc++.h>
const int INF = 0x3f3f3f3f;
inline int min(int a,int b){return a > b? b : a;}
inline int max(int a,int b){return a < b? b : a;}
inline int read(long long &x){
x = ;char ch = getchar();char c = ch;
while(ch > '' || ch < '')c = ch, ch = getchar();
while(ch <= '' && ch >= '')x = x * + ch - '',ch = getchar();
if(c == '-') x = -x;
}
long long gcd(long long a, long long b)
{
long long tmp;
while(b > )
{
tmp = a % b;
a = b;
b = tmp;
}
return a;
} long long x,y,k,j;
int ans;
int main(){
read(x);read(y);
k = x * y;
y >>= ;
for(long long i = x;i <= y;i +=x)
{
j = k / i;
if(i > j)break;
if(j * i == k && gcd(i, j) == x)ans ++;
}
printf("%d", ans << );
return ;
}

最新文章

  1. java笔记--理解java类加载器以及ClassLoader类
  2. Android 样式 (style) 和主题(theme)
  3. Scalaz(13)- Monad:Writer - some kind of logger
  4. Qt知识点、疑难杂症的治疗
  5. 常见makefile写法
  6. 1.2 Python基本语法
  7. mysql根据汉字首字母排序[转]
  8. 部署ionic开发环境
  9. 移动UI框架
  10. 【BZOJ】 1041: [HAOI2008]圆上的整点
  11. HDU1542-Atlantis【离散化&amp;线段树&amp;扫描线】个人认为很全面的详解
  12. docker:Dockerfile构建LNMP平台
  13. 小议常被忽略的a标签:visited属性的特殊用法
  14. 获得硬盘的ID序列号(XE10.1+WIN8.1)
  15. 清空messages方法
  16. Android——sqlite3 基本命令操作
  17. PHP 中使用explode()函数切割字符串为数组
  18. python langid实现语种识别
  19. 题解P3951【小凯的疑惑】
  20. VueJS路由

热门文章

  1. Windows进程创建的流程分析
  2. VS2010-MFC(对话框:为对话框添加控件)
  3. Attribute类的使用
  4. spark生态圈简介
  5. OSG实现利用菲波那契网格(Fibonacci lattice 或 Fibonacci grid)均分球面
  6. 使用传统javaweb进行文件上传
  7. 将数组按指定个数分割,并以&quot;|&quot;做分割
  8. ACM常用的Java代码
  9. Python,anaconda及pycharm安装过程笔记
  10. Trie性能分析之敏感词过滤golang