P1029 [NOIP2001 普及组] 最大公约数和最小公倍数问题 题解

P1029 [NOIP2001 普及组] 最大公约数和最小公倍数问题 题解

黄衣哥
2022-01-19 / 0 评论 / 29 阅读 / 正在检测是否收录...
温馨提示:
本文最后更新于2022年03月28日,已超过61天没有更新,若内容或图片失效,请留言反馈。

[题目传送门]了解一下?(https://www.luogu.com.cn/problem/P1029)

[AC记录]再了解一下?(https://www.luogu.com.cn/record/40439298)

众所周知,两个数相乘=这两个数的最大公约和最小公倍数相乘,so

上代码!!!

#include<bits/stdc++.h> 
using namespace std;
int gcd(int a,int b)//最大公约数
{
    if(a==0)
    {
        return b;
    }
    return gcd(b%a,a);
}
int main() 
{
    int x,y,i,j,n=0,k;//n为答案
    cin>>x>>y;
    for(i=x;i<=y;i++)最大公约数肯定要小于等于原数,最小公倍数肯定要大于等于原数,所以范围就出来了
    {
        if((x*y)%i==0)//如果两个数相乘=这两个数的最大公约和最小公倍数相乘,转化一下就是其中一个数=这两个数的最大公约和最小公倍数相乘/另一个数,前提是除得开
        {
            j=(x*y)/i;
            if(gcd(i,j)==x)//最大公约数是x
                n++;//答案+1
        }
    }
    cout<<n;
    return 0;
}
0

评论 (0)

取消