信息学奥赛一本通 1915：【01NOIP普及组】最大公约数与最小公倍数 | 洛谷 P1029 [NOIP2001 普及组] 最大公约数和最小公倍数问题

【题目链接】

ybt 1915：【01NOIP普及组】最大公约数与最小公倍数
洛谷 P1029 [NOIP2001 普及组] 最大公约数和最小公倍数问题

【题目考点】

1. 最大公约数与最小公倍数

• 求最大公约数的方法：见信息学奥赛一本通 1207：求最大公约数问题 | OpenJudge 2.2 7592:求最大公约数问题
• 最大公约数与最小公倍数的关系：两数乘积为这两数最大公约数与最小公倍数的乘积

【解题思路】

已知两个正整数x,y。x是p,q两个数的最大公约数，y是p,q两个数的最小公倍数。
因为两数乘积是最大公约数与最小公倍数的乘积，所以有：$xy=pq$
p,q这两个数字，一定都大于等于最大公约数x，小于等于最小公倍数y。
从x到y枚举p，通过$q=xy/p$得到q。
求出p,q的最大公约数，看最大公约数的值是否等于x。如果是，那么这一组p, q是满足条件的，做计数。否则不满足条件。
最后输出满足条件的p, q的个数。

【题解代码】

解法1：使用迭代方法求最大公约数

#include
using namespace std;
int gcd(int a, int b)//求a, b的最大公约数。注意必须满足a >= b
{
    int r;
    while(b > 0)
    {
        r = a % b;
        a = b;
        b = r;
    }
    return a;
}
int main()
{
    int x, y, p, q, ct = 0, x1;
    cin >> x >> y;
    for(p = x; p <= y; ++p)
    {
        if(x*y%p == 0)
        {
            q = x*y/p;
            x1 = gcd(p, q);//求出p, q的最大公约数x1 
            if(x1 == x)//如果与x相同，那么这一组p, q满足条件 
                ct++;
        }
    }
    cout << ct;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

解法2：使用递归方法求最大公约数

#include
using namespace std;
int gcd(int a, int b)//求a, b的最大公约数。注意必须满足a >= b
{
	if(b == 0)
		return a;
	return gcd(b, a%b);
}
int main()
{
    int x, y, p, q, ct = 0;
    cin >> x >> y;
    for(p = x; p <= y; ++p)
        if(x*y%p == 0 && gcd(p, x*y/p) == x) 
            ct++;
    cout << ct;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18