Description
Write a program which computes the greatest common divisor (GCD) and the least common multiple (LCM) of given a and b (0 < a, b ≤ 2,000,000,000). You can supporse that LCM(a, b) ≤ 2,000,000,000.
Input
Input consists of several data sets. Each data set contains a and b separated by a single space in a line. The input terminates with EOF.
Output
For each data set, print GCD and LCM separated by a single space in a line.
Sample Input
8 6 50000000 30000000
Output for the Sample Input
2 24 10000000 150000000
题意:
给出 a 和 b(0 <= a,b <= 2000000000),算出 a 和 b 的最大公约数(GCD)和最小公倍数(LCM)。
思路:
GCD。LCM = (A * B)/ GCD。注意写法:
1.2 * 10 ^ 9 不会超int,故可以用 int 型,故 gcd 返回的值可以是 int;
2.LCM 的 A * B 的时候有可能会爆 int 故相除后乘,写成 A / GCD (A,B) * B,有可能最后相乘的时候也会爆 int ,所以最好将其一转化为long long;
3.不需要将 A 和 B 比较大小再GCD,因为当 A < B,第一次递归的时候 GCD(B,A % B)会等于 GCD(A,B)(因为 A % B == B)。
AC:
#include <stdio.h> int gcd(int a,int b) { return (b ? gcd(b,a % b): a); } int main() { int a,b; while(~scanf("%d%d",&a,&b)) { printf("%d %lld\n",gcd(a,b),a / gcd(a,b) * (long long)b); } return 0; }
相关推荐
gcd和lcm 3 一般gcd 3 快速gcd 4 扩展gcd 4 gcd和lcm相关公式衍生 4 三-素数问题 6 素数性质 6 素数猜想 6 素数测试 6 筛素数 7 区间筛素数 7 大素数测试 7 素因子相关 8 梅森素数 8 筛可以表示成x^2+(x+1)^2的素数 ...
在计算机编程中,经常需要处理与数字相关的各种问题,其中包括求两个或多个整数的最小公倍数(LCM)。最小公倍数是一个在多个整数集合中共有的...即,对于任意两个正整数a和b,有公式:a * b = GCD(a, b) * LCM(a, b)。
Advanced Scientific Calculator具有数...*生成随机数,组合,排列,GCD,LCM *混合分数,分数,小数,重复小数,极坐标结果 *统计计算,回归计算,正态分布 什么是新的 3.4.2 增加了更多功能 修复了一些错误
ESBMagnitude,ESBMean,ESBSec,ESBSinCos,ESBSinh,ESBTan,ESBTanh,Extended2DMS,ExtMod,ExtRem,FactorialX,FloatIsNegative,FloatIsPositive,FloatIsZero,Gamma,GCD,GeometricMean,Get87ControlWord,GetMedian,...
数学 Math 模块添加了许多扩展 Elixir 标准库的有用函数。 一般功能 a <~> b比较浮点数,以检查它们是否有效相等(如果它们的绝对差小于@epsilon )。 Math.pow(x, n)算术求幂。 适用于整数幂和浮点数。 Math...
(gcd,lcm,extgcd,mod逆数,底数,中国剰余定理,Garnerのアルゴリズム) 素数・约数 素数・约数に关するアルゴリズム。 (约数列挙,素因数分解,素数决定,エラトステネスの筛) 剰余演算 剰余演算に关するアル...
一、MATLAB常用的基本数学函数 5 abs(x):纯量的绝对值或向量的长度 5 angle(z):复数z的相角(Phase angle) 5 sqrt(x):开平方 5 real(z):复数z的实部 6 imag(z):复数z的虚部 6 conj(z):复数z的共轭复数 6 rats(x...
数学算法 这只是一个简单的Android应用程序,用于演示在我的离散数学课程中使用的一些算法。 这将在整个学期中添加。 ...LCM(使用LCM = a * b / GCD(a,b) 素因数分解(使用简单,低效的算法)
gcdlcm.cpp 时间复杂度-O(log(max(a,b))) gcd(a, b)返回a和b的最大公约数, lcm(a, b)返回a和b的最小公倍数。c 时间复杂度-O(sqrt(n)) phi(n)返回1和n之间的整数,它们是n的互质数。isPrime.cpp 时间...
最大公约数(Greatest Common Divisor,简称GCD)是指两个或多个整数共有约数中最大的一个。例如,对于整数12和18,它们的最大公约数是6。 最小公倍数(Least Common Multiple,简称LCM)则是指能被两个或多个整数...
组合数学(概率-组合-排列-矩阵..) 计算几何 原始操作 直觉 多边形内部,外部 实施 CCW 不可变点 ADT 凸包 最近对问题 线交点 排序 快速排序 计数排序 归并排序 搜索 二分查找 三元搜索 图论 深度优先搜索 (DFS) ...
使用Euclid算法的最大公约数(GCD) 最小公倍数(LCM) 整数平方根 斐波那契数 泛指数字 回文数 毕达哥拉斯三元组 该库中的函数可用于解决休闲数学和编程问题,例如Euler项目中的问题。 安装 通过使用的Python包索引...
1577 GCD & LCM 简单题,分区联赛的题…… 1005 Jugs 简单题 1543 Stripies 简单题 1569 Partial Sums 简单题 1062 Trees Made to Order 简单题 1070 Bode Plot 简单题 1073 Round and Round We Go 简单...
2.2 最小公倍数lcm 22 2.3 快速幂取模B^LmodP(O(logb)) 22 2.4 Fermat小定理 22 2.5 Rabin-Miller伪素数测试 22 2.6 Pollard-rho 22 2.7 扩展欧几里德算法extended-gcd 24 2.8 欧拉定理 24 2.9 线性同余方程ax≡b...
2.2 最小公倍数lcm 22 2.3 快速幂取模B^LmodP(O(logb)) 22 2.4 Fermat小定理 22 2.5 Rabin-Miller伪素数测试 22 2.6 Pollard-rho 22 2.7 扩展欧几里德算法extended-gcd 24 2.8 欧拉定理 24 2.9 线性同余方程ax≡b...
3.2 最大公约数(GCD) 72 3.3 最小公倍数(LCM) 74 3.4 斐波那契数列 75 3.5 素数判定 76 3.6 素数筛选 78 3.7 分解素因数 81 3.8 二分快速幂 83 3.9 常见数学公式总结 85 3.10 规律神器OEIS 87 第四章 ...
1577 GCD & LCM 简单题,分区联赛的题…… 1005 Jugs 简单题 1543 Stripies 简单题 1569 Partial Sums 简单题 1062 Trees Made to Order 简单题 1070 Bode Plot 简单题 1073 Round and Round We Go 简单...
包括什么到目前为止,我已经为以下内容创建了 API: 数学GCD(最大公约数)。 LCM(最小公倍数)。 向量 2 点积; 量级; 减法和加法矢量投影2x2 方程组因式分解没有 BigInteger 的模块化字段中的算术模块化添加模...
数学函数可以智能地处理Clojure数字塔中的各种类型,以及Scheme实现中常见的数学函数。 功能包括: (expt xy)-x的yth次方 (abs n)-n的绝对值 (gcd mn)-m和n的最大公约数 (lcm mn)-m和n的最小公倍数 (第x...
·FLOOR ·GCD ·INT ·LCM ·LN ·LOG ·LOG10 ·MDETERM ·MINVERSE ·MMULT ·MOD ·MROUND ·MULTINOMIAL ·ODD ·PI ·POWER ·PRODUCT ·QUOTIENT ·RADIANS ·RAND ·RANDBETWEEN ·ROMAN ·ROUND ·ROUND...