当前位置：网站首页>2513: 小勇学分数（公约数问题）

2513: 小勇学分数（公约数问题）

2022-07-27 00:36:00 【51CTO】

2513: 小勇学分数

Time Limit: 1 Sec Memory Limit: 128 MB

Submit: 1140

Solved: 794

[

Submit][

Status][

Web Board]

Description

小慧的弟弟小勇刚学分数，小慧想检查弟弟约分是否正确。请你编程序帮帮她吧。

输入m/n 形式的分数，输出约分后的分数（能整除的只输出整数）

Input

两个数m和n（1<=n,m<=1000）

Output

约分后的分数

Sample Input

Sample Output

HINT

提示：输入的数据中注意'/'的匹配，输出结果如果是整数不输出分母

AC代码：

       
       #include <stdio.h>
       
       #include <stdlib.h>
       
       int 
       
       gcd (
       
       int 
       
       a,
       
       int 
       
       b)
       
{
       
       while(
       
       a
       
       !=
       
       b)
       
    {
       
       if(
       
       a
       
       >
       
       b)
       
       a
       
       =
       
       a
       
       -
       
       b;
       
       if(
       
       b
       
       >
       
       a)
       
       b
       
       =
       
       b
       
       -
       
       a;
       
    }
       
       return 
       
       a;
       
}
       
       int 
       
       main()
       
{
       
       int 
       
       m,
       
       n;
       
       scanf(
       
       "%d/%d",
       
       &
       
       m,
       
       &
       
       n);
       
       int 
       
       q
       
       =
       
       gcd(
       
       m,
       
       n);
       
       int 
       
       x
       
       =
       
       m
       
       /
       
       q,
       
       y
       
       =
       
       n
       
       /
       
       q;
       
       if(
       
       x
       
       %
       
       y
       
       ==
       
       0)
       
       printf(
       
       "%d",
       
       x
       
       /
       
       y);
       
       else
       
       printf(
       
       "%d/%d\n",
       
       x,
       
       y);
       
       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.

归纳下最小公倍数和最大公约数

       
       /*最小公倍数LCM(Lowest Common multiple)
       
       最大公约数GCD(greastest common divisor)
       
       */
       
       int 
       
       gcd (
       
       int 
       
       a,
       
       int 
       
       b)
       
       //更相减损术（中）
       
{
       
       while(
       
       a
       
       !=
       
       b)
       
    {
       
       if(
       
       a
       
       >
       
       b)
       
       a
       
       =
       
       a
       
       -
       
       b;
       
       if(
       
       b
       
       >
       
       a)
       
       b
       
       =
       
       b
       
       -
       
       a;
       
    }
       
       return 
       
       a;
       
}
       
       int 
       
       gcd(
       
       int 
       
       x,
       
       int 
       
       y)  
       
       //辗转相除法（外）
       
{  
       
       int 
       
       r;  
       
       while(
       
       y
       
       >
       
       0)  
       
    {  
       
       r
       
       =
       
       x
       
       %
       
       y;  
       
       x
       
       =
       
       y;  
       
       y
       
       =
       
       r;  
       
    }  
       
       return 
       
       x;  
       
}  
       
       int 
       
       lcm(
       
       int 
       
       x,
       
       int 
       
       y)  
       
{  
       
       return 
       
       x
       
       *
       
       y
       
       /
       
       gcd(
       
       x,
       
       y);  
       
}
      
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.