GCD and LCM

GCD and LCM

	///Euclidean algorithm for computing the greatest common divisor
	///O(logmin(a,b)).
	#include <bits/stdc++.h>
	using namespace std;
	#define INF 1<<30
	#define MAX 10005
	#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	typedef long long ll;
	ll lcm(ll a, ll b)
	{
	return (a)/ __gcd(a, b) * b;
	}
	int main()
	{
	FASTIO
	///*
	//double start_time = clock();
	#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	freopen("error.txt", "w", stderr);
	#endif
	//*/
	int T;
	cin >> T;
	while(T--){
	ll a,b;
	cin >> a >> b;
	cout << __gcd(a, b)<< " "<<lcm(a, b);
	if(T)cout << endl;
	}
	//double end_time = clock();
	//printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000);
	return 0;
	}

view raw gcd&lcm.cpp hosted with ❤ by GitHub

	///Euclidean algorithm for computing the greatest common divisor
	///O(logmin(a,b)).
	#include <bits/stdc++.h>
	using namespace std;
	#define INF 1<<30
	#define MAX 10005
	#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	typedef long long ll;
	int gcd1(int a, int b)
	{
	if(b == 0) return a;
	else
	return gcd(b, a % b);
	}
	int gcd2(int a, int b)
	{
	return b ? gcd(b, a % b) : a;
	}
	int gcd3(int a, int b)
	{
	while(b){
	a %= b;
	swap(a,b);
	}
	return a;
	}
	int gcd4(int a, int b)
	{
	return __gcd(a, b); // builtin
	}
	int lcm(int a, int b)
	{
	return a / gcd(a, b) * b;
	}
	int main()
	{
	FASTIO
	///*
	//double start_time = clock();
	#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	freopen("error.txt", "w", stderr);
	#endif
	//*/
	//double end_time = clock();
	//printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000);
	return 0;
	}

view raw gcd.cpp hosted with ❤ by GitHub

Share: