GitBook

这里写图片描述

复习了一下最大公约数的递归 (话说上次还是用的辗转相减) 嗯…… 还真有点忘……

int gcd(int a,int b) {
	if(b==0) {
		return a;
	}
	return gcd(b,a%b);
}

题目AC代码

#include<stdio.h>
int gcd(int a,int b) {
	if(b==0) {
		return a;
	}
	return gcd(b,a%b);
}
int main() {
	int T;
	scanf("%d",&T);
	while(T--) {
		int a,b;
		scanf("%d %d",&a,&b);
		printf("%d %d\n",gcd(a,b),a*b/gcd(a,b));
	}
	return 0;
}

标程也是辗转相除 但没用递归函数 用的循环写的

#include<stdio.h>
int main() {
	unsigned int u,v,r,s,i,d;
	scanf("%u",&s);
	for(i=1; i<=s; i++) {
		scanf("%u%u",&u,&v);
		d=u*v;
		while(v!=0) {
			r=u%v;
			u=v;
			v=r;
		}
		printf("%u %u\n",u,d/u);
	}
	return 0;
}

题目地址:【NYOJ】[40]公约数和公倍数