[已解决]最大公约数

辞树

函数1（最大公约数）
题目描述

输入两个正整数m和n（1<m, n<1000000000），求其最大公约数和最小公倍数。

输入

有多行，每行2个正整数m和n。

输出

m和n的最大公约数、最小公倍数。

样例输入

16 24

5 7

样例输出

8 48

1 35

提示

要求：编写求最大公约数和最小公倍数的函数。

这格式怎么弄呀

最佳答案

月排行榜 / 总排行榜

jackz007

2021-11-25 15:22:15

#include <stdio.h>

int gcd(int m , int n)
{
        int d , k                                                                                     ;
        if(! (m % n)) d = n                                                                           ;
        else if(! (n % m)) d = m                                                                      ;
        else for(d = 1 , k = 2 ; k < m && k < n ; k ++) if(! (m % k) && ! (n % k)) d = k              ;
        return d                                                                                      ;
}

int lcm(int m , int n)
{
        return m * n / gcd(m , n)                                                                     ;
}

int main(void)
{
        int d[2000][2] , i , j , k , n                                                                ;
        scanf("%d" , & n)                                                                             ;
        for(i = 0 ; i < n ; i ++) scanf("%d%d" , & d[i][0] , & d[i][1])                               ;
        for(i = 0 ; i < n ; i ++) printf("%d %d\n" , gcd(d[i][0] , d[i][1]) , lcm(d[i][0] , d[i][1])) ;
}

        编译、运行实况：

D:\0002.Exercise\C>g++ -o x x.c

D:\0002.Exercise\C>x
2
16 24
5 7
8 48
1 35

D:\0002.Exercise\C>

跳转到最佳答案楼层

Gacy

用递归

jackz007

#include <stdio.h>

int gcd(int m , int n)
{
        int d , k                                                                                     ;
        if(! (m % n)) d = n                                                                           ;
        else if(! (n % m)) d = m                                                                      ;
        else for(d = 1 , k = 2 ; k < m && k < n ; k ++) if(! (m % k) && ! (n % k)) d = k              ;
        return d                                                                                      ;
}

int lcm(int m , int n)
{
        return m * n / gcd(m , n)                                                                     ;
}

int main(void)
{
        int d[2000][2] , i , j , k , n                                                                ;
        scanf("%d" , & n)                                                                             ;
        for(i = 0 ; i < n ; i ++) scanf("%d%d" , & d[i][0] , & d[i][1])                               ;
        for(i = 0 ; i < n ; i ++) printf("%d %d\n" , gcd(d[i][0] , d[i][1]) , lcm(d[i][0] , d[i][1])) ;
}

        编译、运行实况：

D:\0002.Exercise\C>g++ -o x x.c

D:\0002.Exercise\C>x
2
16 24
5 7
8 48
1 35

D:\0002.Exercise\C>

辞树

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

谢谢您！

辞树

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

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

Gacy

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

jjiahe

#include<stdio.h>
int gcd(long x,long y){
        if(y==0) return x;
        return gcd(y,x%y);
}
int main(){
        int m,n;
        while(scanf("%d%d",&m,&n)==2){
                int t=gcd(m,n);
                long lcm=m/t*n;
                printf("%d %lld\n",t,lcm);
        }
}