[ACM/算法]eoj2517辗转相除计算最小公倍数，公式法计算最大公约数

Posted on | Edited on | In | Comments: 
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
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[])
 {
 int n,a,b;
 scanf(“%d”,&n);
 while(n–){
 scanf(“%d %d”,&a,&b);
 printf(“%d %d\n”,GCD(a,b),a*b/GCD(a,b));
 }
 system(“pause”);
 return 0;
 }
 void
 change(int *a,int *b){
 int temp;
 temp = *a;
 *a = *b;
 *b = temp;
 }
 int
 GCD(int a,int b){
 int x;
 while(b)
 {
 if(a<b){
 change(&a, &b); //
 }
 x = a % b;
 a = b;
 b = x;
 }
 return a;
 }
 其中 a*

b/GCD(a,b) 为计算最小公倍数的公式。