最大公约数 c++_3和4的最小公倍数

老牧童 • 2023-10-06 17:45 • 未分类 • 阅读 197

大家好，欢迎来到IT知识分享网。

题目链接

题目描述 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

以输入3 60为例

看道题目，我最开始的思路是：根据结论，两个自然数的最大公约数与它们的最小公倍数的乘积等于这两个数的乘积。

1. 先得到两数之积，再分解之：180 = 2x2x3x3x5，因子用数组来保存。

2. 再排列组合得到两个数，判断他们是否满足两数最大公约数值为3的条件,但是组合起来好像有点麻烦，在网上看到黑桐的算法。

他的算法是：

1.得到所有是3的倍数，是60的约数的集合。num[ ] = {3,6,12,15,30,60}

2.用num[]构造二维矩阵来匹配，看所对应组合是否满足（最大公约数为3 && 最小公倍数为60），但是这样一来复杂度就是O（N2）了。

受到启发，将他的算法进行了改进，得到算法复杂度为O（N）的下面算法：

#include <iostream>
using namespace std;
bool isGcd(int a, int b, int num);
int main(){
    //int x = 3, y = 60;
    int x, y;
    cin >> x >> y;
    int count = 0;
    for (int i = x; i <= y; i += x)
    {
        if (y%i == 0){
            int a = i;//a值依此为 3,6,12,15,30,60
            int b = x*y / i;//根据性质：两个自然数的最大公约数与它们的最小公倍数的乘积等于这两个数的乘积。 b值依此为：60 30 15 12 6 3
            if (isGcd(a, b, x)){//为两数之和为已知180，如果其最大公约为3，那么其最小公倍数一定为60
                count++;
                //cout << a<<" "<< b << " * "; 
                //输出：3 60 * 12 15 * 15 12 * 60 3 *
            };
        }
    }
    cout << count;
    return 0;

}
bool isGcd(int min, int max, int num)//判断num是否为min、max两数的最大公约数
{
    int temp;
    if (min < max){
        swap(min, max);
    }
    while (max != 0){
        temp = min % max;
        min = max;
        max = temp;
    }
    return num == max ? true : false;
}

免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://yundeesoft.com/29572.html