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

比眉伴天荒 2021-11-11 01:10 298阅读 0赞

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

## 题目描述 ##

输入2个正整数x0，y0（2<=x0<100000，2<=y0<=1000000），求出满足下列条件的P，Q的个数。  
  
条件：  
  
1. P，Q是正整数；  
  
2. 要求P，Q以x0为最大公约数，以y0为最小公倍数。  
  
试求：  
  
满足条件的所有可能的两个正整数的个数。

## 输入 ##

每个测试文件包含不超过5组测试数据，每组两个正整数x0和y0（2<=x0<100000，2<=y0<=1000000）。

## 输出 ##

对于每组输入数据，输出满足条件的所有可能的两个正整数的个数。  
  
下面是对样例数据的说明：  
  
输入3 60  
  
此时的P Q分别为:  
  
3 60  
15 12  
12 15  
60 3  
  
所以，满足条件的所有可能的两个正整数的个数共4种。

## 样例输入 ##

3 60

## 样例输出 ##

#include<cstdio>
    
    int g(int n, int m)
    {
        int temp, r;
        if(n < m){ 
            temp = n; 
            n = m; 
            m = temp; 
        } 
        while(m != 0){
            r = n % m;
            n = m; 
            m = r; 
        } 
        return n;
    }
    
    int main()
    {
        int a, b, i, j, count;
        while(~scanf("%d%d", &a, &b)){
            count = 0;
            for(i = a; i <= b; i++)
            {
                for(j = i + 1; j <= b; j++)
                {
                    if(g(i, j) == a && i / g(i,j) * j == b)
                        count++;
                }
                printf("%d\n", 2 * count);
            }
        }
        return 0;
    }

递归法求最小公倍数

#include<iostream>
    using namespace std;
    int gcd(int n,int m)
    {
        if(n<m)
        {
            int temp;
            temp=n;
            n=m;
            m=temp;
        }
        if(n%m==0) return m;
        else return gcd(m,n%m);
    }
    int main()
    {
        int a,b,i,j,num;
        while(cin>>a&&cin>>b)
        {
            num=0;
            for(i=a;i<=b;i++)
            {
                for(j=i;j<=b;j++)
                {
                    if(gcd(i,j)==a&&i/gcd(i,j)*j==b) num++;
                }
            }
            cout<<2*num<<endl;
        }
        return 0;
    }

转载于:https://www.cnblogs.com/qing123tian/p/11110915.html