[已解决]最大公约数

辞树

1. 函数1（最大公约数）
   
2. 题目描述
   
3. 
   
4. 输入两个正整数m和n（1<m, n<1000000000），求其最大公约数和最小公倍数。
   
5. 
   
6. 输入
   
7. 
   
8. 有多行，每行2个正整数m和n。
   
9. 
   
10. 输出
    
11. 
    
12. m和n的最大公约数、最小公倍数。
    
13. 
    
14. 样例输入
    
15. 
    
16. 16 24
    
17. 
    
18. 5 7
    
19. 
    
20. 样例输出
    
21. 
    
22. 8 48
    
23. 
    
24. 1 35
    
25. 
    
26. 提示
    
27. 
    
28. 要求：编写求最大公约数和最小公倍数的函数。
    
29. 
    
30. 
    

复制代码

这格式怎么弄呀

最佳答案

月排行榜 / 总排行榜

jackz007

2021-11-25 15:22:15

1. #include <stdio.h>
   
2. 
   
3. int gcd(int m , int n)
   
4. {
   
5.         int d , k                                                                                     ;
   
6.         if(! (m % n)) d = n                                                                           ;
   
7.         else if(! (n % m)) d = m                                                                      ;
   
8.         else for(d = 1 , k = 2 ; k < m && k < n ; k ++) if(! (m % k) && ! (n % k)) d = k              ;
   
9.         return d                                                                                      ;
   
10. }
    
11. 
    
12. int lcm(int m , int n)
    
13. {
    
14.         return m * n / gcd(m , n)                                                                     ;
    
15. }
    
16. 
    
17. int main(void)
    
18. {
    
19.         int d[2000][2] , i , j , k , n                                                                ;
    
20.         scanf("%d" , & n)                                                                             ;
    
21.         for(i = 0 ; i < n ; i ++) scanf("%d%d" , & d[i][0] , & d[i][1])                               ;
    
22.         for(i = 0 ; i < n ; i ++) printf("%d %d\n" , gcd(d[i][0] , d[i][1]) , lcm(d[i][0] , d[i][1])) ;
    
23. }

复制代码

        编译、运行实况：

1. D:\0002.Exercise\C>g++ -o x x.c
   
2. 
   
3. D:\0002.Exercise\C>x
   
4. 2
   
5. 16 24
   
6. 5 7
   
7. 8 48
   
8. 1 35
   
9. 
   
10. D:\0002.Exercise\C>

复制代码

跳转到最佳答案楼层

Gacy

用递归

jackz007

1. #include <stdio.h>
   
2. 
   
3. int gcd(int m , int n)
   
4. {
   
5.         int d , k                                                                                     ;
   
6.         if(! (m % n)) d = n                                                                           ;
   
7.         else if(! (n % m)) d = m                                                                      ;
   
8.         else for(d = 1 , k = 2 ; k < m && k < n ; k ++) if(! (m % k) && ! (n % k)) d = k              ;
   
9.         return d                                                                                      ;
   
10. }
    
11. 
    
12. int lcm(int m , int n)
    
13. {
    
14.         return m * n / gcd(m , n)                                                                     ;
    
15. }
    
16. 
    
17. int main(void)
    
18. {
    
19.         int d[2000][2] , i , j , k , n                                                                ;
    
20.         scanf("%d" , & n)                                                                             ;
    
21.         for(i = 0 ; i < n ; i ++) scanf("%d%d" , & d[i][0] , & d[i][1])                               ;
    
22.         for(i = 0 ; i < n ; i ++) printf("%d %d\n" , gcd(d[i][0] , d[i][1]) , lcm(d[i][0] , d[i][1])) ;
    
23. }

复制代码

        编译、运行实况：

1. D:\0002.Exercise\C>g++ -o x x.c
   
2. 
   
3. D:\0002.Exercise\C>x
   
4. 2
   
5. 16 24
   
6. 5 7
   
7. 8 48
   
8. 1 35
   
9. 
   
10. D:\0002.Exercise\C>

复制代码

辞树

jackz007 发表于 2021-11-25 15:22
编译、运行实况：

谢谢您！

辞树

Gacy 发表于 2021-11-25 15:18
用递归

虽然在你们答复前我就写好了，谢谢，果然人不逼自己一把，就不知道自己能做什么

Gacy

辞树 发表于 2021-11-25 15:26
虽然在你们答复前我就写好了，谢谢，果然人不逼自己一把，就不知道自己能做什么

jjiahe

1. #include<stdio.h>
   
2. int gcd(long x,long y){
   
3.         if(y==0) return x;
   
4.         return gcd(y,x%y);
   
5. }
   
6. int main(){
   
7.         int m,n;
   
8.         while(scanf("%d%d",&m,&n)==2){
   
9.                 int t=gcd(m,n);
   
10.                 long lcm=m/t*n;
    
11.                 printf("%d %lld\n",t,lcm);
    
12.         }
    
13. }

复制代码