题解 P1029 【最大公约数和最小公倍数问题】

· · 题解

第二次发题解

第一次没过

楼下居然没有爆？？？用得是递归也！

我三重循环也好不到哪去

好了，进入正题！

首先，我们要知道，两个数的最大公约数和最小公倍数相乘，等于这两个数相乘

最大公约数=P，最小公倍数=Q

第一个数=i，第二个数=j

那么，

P Q= =I j

好，那么，我们就用i代表i，j代表j（雾）

for(int i=p;i<=q;i++)//从p开始，q结束（看题）
{
    for(j=p;j<=q;j++)
    {
        if(i*j==p*q)
    }
}

这只是第一部分。

对于上面的程序，萌新和大佬表示，不会爆吗？

题目的范围是2≤x 0 ​
<100000,2≤y 0 ​
<=1000000

一个程序循环超过一百万次，就会爆，所以，

我也不知道为什么不会爆（狗头）

然后第二部分就是大家熟悉的辗转相除法，若有不会，

请看下回分解

辗转相除法的主要思想是：

A=一个数，B=另一个数

T=A%b

如果T没有等于零，也就是A和B不可以整除，那么，就做以下步骤：

A=B；//被除数变成除数

B=T；//除数变成余数

T=A%B；

用while框柱

那么第二部分就是

int a=i,b=j,t=a%jb;
while(t!=0)
{
    a=b;
    b=t;
    t=a%b;
}

这样就得出了i和j的最大公约数

那么最小公倍数的求法，用到一个公式（不想推导）

最小公倍数=i*j/最大公因数

同时，我们也要完成题目的第二个要求（自已看）

所以要加一个判断，判断P和Q是非是两个数的最大公约数或最小公倍数

第三部分就是以下这个程序：

int op=i*j/b;
if((b==p||b==q)&&(op==p||op==q)) ans++;

好了，这个程序到这就结束了，如果想自己领悟的话，就不要往下翻了，同时我也不会让你们不小心看到这个程序，所以，想要完整程序的话...

（我真应该装个连点器，手痛）

童鞋，认真得告诉我，你翻了多久？？？

#include<iostream>
using namespace std;
int main()
{
    int p,q,ans=0;
    cin>>p>>q;
    for(int i=p;i<=q;i++)
    {
        for(int j=p;j<=q;j++)
        {
            if(j*i==p*q)
            {
                int a=i,b=j,t=a%b;
                while(t!=0)
                {
                    a=b;
                    b=t;
                    t=a%b;
                }
                int op=i*j/b;
                if((b==p||b==q)&&(op==p||op==q)) ans++;
            }
        }
    }
    cout<<ans;
    return 0;
}

谢谢大家这么认真得看到（翻到）这里，我会加油，继续写更多的题解（帮大家作弊）！！！