题目链接:P1029 [NOIP 2001 普及组] 最大公约数和最小公倍数问题

这个题可以先读题,先输入x0和y0,然后需要求P,Q,这两个数的最大公约数是x0,最大公倍数是y0.求有多少个这样的P,Q

我们简单的想到穷举.因为x0是两个数字的公约数,那这个数一定能被x0整除,所以我们从x0穷举,步长为x0即可.因为两个数的最小公倍数为y0,那么这两个数一定是小于等于y0的.

python代码如下:

def gcd(a,b):
    return a if b==0 else gcd(b,a%b)
x0,y0=map(int,input().split())
count=0
for i in range(x0,y0+1,x0):
    for j in range(x0,y0+1,x0):
        if gcd(i,j)==x0 and i*j//gcd(i,j)==y0:
            count+=1
print(count)

c++代码如下:

#include<iostream>
using namespace std;
#include<cmath>
#define int long long
int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b, a % b);
}
int lcm(int a, int b)
{
    return abs(a * b) / gcd(a, b);
}
signed main()
{
    ios::sync_with_stdio;
    cin.tie();
    int x0, y0;
    cin >> x0 >> y0;
    int count = 0;
    for (int i = x0; i <= y0; i+=x0)
    {
        for (int j = x0; j <= y0; j+=x0)
        {
            if (gcd(i, j) == x0 && lcm(i, j) == y0)
            {
                count++;
            }
        }
    }
    cout << count;
}

样例只能过8个,还有两个过不去的,因为在比较极端的情况下,例如x0是2,y0是100000,那么也要遍历50000次,并且这是一个双层的循环,执行几千万次,那就会超时了.

这个题需要利用一个性质,因为$lcm(x,y)=\frac{x\times y}{gcd(x,y)}$,所以$gcd(x,y)\times lcm(x,y)=x\times y $,也就是gcd和lcm相乘之后约分掉分母,就剩下x和y了.然后现在我们知道了gcd,也知道了lcm,穷举x然后求y就行了.直接就把双层循环变成了单层循环,效率大大提高.

cpp代码如下:

#include<iostream>
using namespace std;
#include<cmath>
#define int long long
int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b, a % b);
}
int lcm(int a, int b)
{
    return abs(a * b) / gcd(a, b);
}
signed main()
{
    ios::sync_with_stdio;
    cin.tie();
    int x0, y0;
    cin >> x0 >> y0;
    int count = 0;
    for (int P = x0; P <= y0; P += x0)
    {
        int Q = (x0 * y0) / P;
        if (gcd(Q, P) == x0 && lcm(Q, P) == y0)
        {
            // cout << P <<" "<< Q <<" "<<gcd(Q,P) << endl;
            count++;
        }
    }
    cout << count;
}

python代码如下:

def gcd(a,b):
    return a if b==0 else gcd(b,a%b)
def lcm(a,b):
    return a*b//gcd(a,b)
x0,y0=map(int,input().split())
count=0
flag=0
for P in range(x0,y0+1,x0):
    Q=x0*y0/P
    if gcd(P,Q)==x0 and lcm(P,Q)==y0:
        count+=1
print(count)

这里我们求完P和Q依然需要进行一个验证,因为$\frac{(x0 \times y0) }{P}$​有可能是一个小数,并不符合条件,所以把这两个数再求一遍gcd和lcm进行验证就可以了.反正都单层循环了,题目给的数据也就到$10^5$而已,多写个判断也问题不大.