[洛谷P1029]最大公约数与最小公倍数问题 题解（辗转相除法求GCD）

时间：2021-07-10 21:30:32

[洛谷P1029]最大公约数与最小公倍数问题

Description

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

条件:1.P,Q是正整数;2.要求P,Q以x0为最大公约数,以y0为最小公倍数.

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

输入格式：二个正整数x0,y0

输出格式：一个数，表示求出满足条件的P,Q的个数

Solution

1.由最大公约数的定义我们得到：存在k1,k2∈R，使P=k1x0,Q =k2x0;

2.由LCM(a,b)GCD(a,b)=ab(LCM为两数小公倍数)，可以得到：x0y0=PQ，带入k1,k2得：y0=k1k2x0,即k1*k2=y0/x0;

3.在本题中我们不妨设P<Q,即k1<k2,那么从1到floor(sqrt(y0/x0))穷举k1即可，判断条件为k1,k2互质;

4.由于k1,k2交换后扔为一组解，所以ans*=2;

5.对于x0=y0的情况，我们经过思考发现解应只有一组，所以要加上特判；

Code

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

using namespace std;

int gcd(int a,int b){return b?gcd(b,a%b):a;} //GCD

int main(){

    int x,y,k1,k2,n,ans=0;

    scanf("%d%d",&x,&y);

    if(x==y){                //特判

        printf("1\n");

        return 0;

    }

    if(y%x!=0){              //无解

        printf("0\n");

        return 0;

    }

    n=y/x;

    for(k1=1;k1<=floor(sqrt(n));++k1){

        if(n%k1==0){

            k2=n/k1;

            if(gcd(k1,k2)==1)ans++;

        }

    }

    printf("%d\n",ans*2);

    return 0;

}

辗转相除法求GCD（欧几里得算法）基础知识部分可以参考我的随笔：http://www.cnblogs.com/COLIN-LIGHTNING/p/8371664.html

相关文章