GCD作为缩写意义有多种。它通常表示最大公约数其基本方法为辗转相除法

题目链接:http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Index/problemdetail/pid/1131.html

代码如下

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int ans(int a,int b){
	if(a==0) return b;
	int r;
	r=a;
	a=b%a;
	b=r;
    ans(a,b);
}
int main(){
	int a,b,m,n;
	scanf("%d %d",&a,&b);
	if(a>b) swap(a,b);
	n=ans(a,b);
	m=a*b/n;
	printf("%d\n",n);
	printf("%d\n",m);
	return 0;
}

gcd在c++中有相应函数(–gcd)【位于algorithm】(大赞stl神教)

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int main(){
	int a,b;
	scanf("%d %d",&a,&b);
	int n=__gcd(a,b);
	printf("%d\n",n);
	printf("%d\n",(a*b/n));
	return 0;
}

发表回复