Informatics Olympiad 1915: [01NOIP Popularization Group] Greatest Common Divisor and Least Common Multiple | Luogu P1029 [NOIP2001 Popularization Group] The problem of the greatest common divisor and

【题目链接】

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

【题目考点】

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

• 求最大公约数的方法：见信息学奥赛一本通 1207：求最大公约数问题 | OpenJudge 2.2 7592:求最大公约数问题
• 最大公约数与最小公倍数的关系：The product of two numbers is the product of the greatest common divisor and the least common multiple of the two numbers

【解题思路】

已知两个正整数x,y.x是p,q两个数的最大公约数,y是p,q两个数的最小公倍数.
Because the product of two numbers is the product of the greatest common divisor and the least common multiple,所以有：$xy=pq$
p,q这两个数字,must be greater than or equal to the greatest common divisorx,Less than or equal to the least common multipley.
从x到y枚举p,通过$q=xy/p$得到q.
求出p,q的最大公约数,See if the value of the greatest common divisor is equalx.如果是,那么这一组p, q是满足条件的,做计数.否则不满足条件.
The final output that satisfies the conditionsp, q的个数.

【题解代码】

解法1：Use the iterative method to find the greatest common divisor

#include<bits/stdc++.h>
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;
}

解法2：Use recursive methods to find the greatest common divisor

#include<bits/stdc++.h>
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;
}