【洛谷】P1029 [NOIP2001 普及组] 最大公约数和最小公倍数问题

川长思鸟来 2022-09-07 01:23 187阅读 0赞

# 1. 题目 #

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

# 2. 思想 #

*  定一个 `gcd()` 函数，用于取两个数的最大公约数
 *  两重for循环遍历，找出合适的值即可  
    注意`for`循环的边界问题，`i/j`的step可以调成 最大公约数，同时其二者的上界都可以写为 `sqrt(x *y)`。如果单纯的写成`i<=y`会导致`TLE`错误。

其实两重 `for` 循环的复杂度还是欠妥，可以优化成 O(n)。 => 这类问题都可以简化成，如果两个变量存在关联，那么我们就得考虑是否只要控制其中一个变量即可讨论完成了？

# 3. 代码 #

#include<iostream>
    #include<cmath>
    using namespace std;
    typedef long long ll;
    
    //求a,b的最大公约数 
    int gcd(int a,int b){ 
    	int remain = a;
    	while(remain){ 
    		remain = a%b;
    		a = b;
    		b = remain;		
    	}
    	return a;
    }
    
    int main(){ 
    	ll x ,y ;
    	cin >> x >> y; //输入两个数
    	int res = 0;
    	int flag = 0;
    	//1.该数的范围一定不会超过最小公倍数y
    	
    	ll prod = x * y;
    	for (int i = x;i<= sqrt(prod);i+=x){  //2.可以修改step
    		for (int j = y;j>=sqrt(prod);j-=x){ 
    			int a = gcd(i,j);
    			ll b = j*i/a; //求出最大公约数 
    			if( a == x && b==y){ 
    				if (i == j) flag = 1;
    				res++;
    			}			
    		}
    	} 
    	cout << res * 2 - flag ;	
    }

[P1029]: https://www.luogu.com.cn/problem/P1029

发表评论取消回复

表情：

评论列表（有 0 条评论，187人围观）

还没有评论，来说两句吧...

相关阅读

相关【洛谷】P1029 [NOIP2001 普及组] 最大公约数和最小公倍数问题

1. 题目 [P1029][] 最大公约数和最小公倍数问题 2. 思想定一个 `gcd()` 函数，用于取两个数的最大公约数两重for循环遍历，找

川长思鸟来/ 2022年09月07日 01:23/ 0 赞/ 188 阅读

相关【洛谷】P1028 [NOIP2001 普及组] 数的计算

题目题目[链接][Link 1] 题目要读两遍才能理解讲什么，主要意思就是让你找出一个数可以被分裂形成多少个数？分裂的规则是，不能比该数最左侧的数的一半儿大。

分手后的思念是犯贱/ 2022年09月07日 01:20/ 0 赞/ 173 阅读

相关最大公约数和最小公倍数

从键盘上输入两个整数m和n,求其最大公约数。辗转相除法 include<stdio.h> int main() { int

骑猪看日落/ 2022年08月02日 06:43/ 0 赞/ 189 阅读

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

题目描述 Description 输入二个正整数x0,y0(2<=x0<100000,2<=y0<=1000000),求出满足下列条件的P,Q的个数条件: 1.P,Q是

秒速五厘米/ 2022年06月16日 08:41/ 0 赞/ 151 阅读

相关洛谷P1029 最大公约数和最小公倍数问题

题目描述输入二个正整数x0,y0(2<=x0<100000,2<=y0<=1000000),求出满足下列条件的P,Q的个数条件: 1.P,Q是正整数 2.要求P

短命女/ 2022年05月28日 22:23/ 0 赞/ 137 阅读

相关 NOIP 2001 最大公约数和最小公倍数问题(暴力)

题目描述输入二个正整数x0，y0（2<=x0<100000，2<=y0<=1000000），求出满足下列条件的P，Q的个数。条件： 1. P，A是正整数； 2

淡淡的烟草味﹌/ 2022年05月17日 09:09/ 0 赞/ 161 阅读

相关最大公约数和最小公倍数

最大公约数我们要考虑这种情况，48 和 24 这种情况，48是24的二倍，我们仔细观察的话会发现，如果不是这种特殊情况，其它的情况就是，两个数最大的公约数也不会超过那个最小数的

我不是女神ヾ/ 2022年05月13日 01:50/ 0 赞/ 212 阅读

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

最大公约数和最小公倍数问题题目描述输入2个正整数x0，y0（2<=x0<100000，2<=y0<=1000000），求出满足下列条件的P，Q的个数。

比眉伴天荒/ 2021年11月11日 01:10/ 0 赞/ 261 阅读

相关最小公倍数和最大公约数

一、最大公约数 1、辗转相除法 int getZuixiaogongyueshu(int num1,int num2){ int temp=0;

阳光穿透心脏的1/2处/ 2021年09月12日 02:20/ 0 赞/ 368 阅读

相关最小公倍数和最大公约数

最大公约数求最大公约数最常见的办法是辗转相除法代码实现: 递归 int gcd(int a, int b){ return b == 0

ゞ浴缸里的玫瑰/ 2021年06月24日 13:58/ 0 赞/ 383 阅读