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

题目描述

输入两个正整数 $x_0, y_0$，求出满足下列条件的 $P, Q$ 的个数：

  1. $P,Q$ 是正整数。

  2. 要求 $P, Q$ 以 $x_0$ 为最大公约数，以 $y_0$ 为最小公倍数。

试求：满足条件的所有可能的 $P, Q$ 的个数。

输入格式

一行两个正整数 $x_0, y_0$。

输出格式

一行一个数，表示求出满足条件的 $P, Q$ 的个数。

样例 #1

样例输入 #1

1
3 60

样例输出 #1

1
4

提示

$P,Q$ 有 $4$ 种：

  1. $3, 60$。
  2. $15, 12$。
  3. $12, 15$。
  4. $60, 3$。

对于 $100%$ 的数据，$2 \le x_0, y_0 \le {10}^5$。

【题目来源】

NOIP 2001 普及组第二题

解题思路

主要思路

第一步：找出既是最大公约数x的倍数，又是最小公倍数y的的因数的数记为num
第二步：找到n，使得nnum=xy
第三步：判断n和num的最大公因数是否为x

完整代码

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<stdio.h>
int change(int num,int x,int y);
int main()
{
    int x,y,num,i=0,right;
    scanf("%d%d",&x,&y);
    num=x;
    while (num<=y)
    {
        if(y%num==0){
            if(change(num,x,y)==1){
               i++;
            }
        }
        num=num+x;
    }
    printf("%d\n",i);
    return 0;
}
int change(int num,int x,int y)
{
    int n;
    n=x*y/num;
    if(min(num,n,x)){
        return 1;
    }
    return 0;
}
int min(int num,int n,int x)
{
    int mid;
    if(num<n){
        mid=num;
        num=n;
        n=mid;
    }
    while(num%n!=0){
        mid=num%n;
        num=n;
        n=mid;
    }
    if(n==x){
        return 1;
    }
    return 0;
}