首页 > 代码库 > 数论——gcd&&lcm
数论——gcd&&lcm
gcd(a, b)，就是求a和b的最大公约数
lcm(a, b)，就是求a和b的最小公倍数
然后有个公式
a*b = gcd * lcm ( gcd就是gcd(a, b)， ( ????? ) 简写你懂吗)
解释（不想看就跳过）{
首先，求一个gcd，然后。。。
a / gcd 和 b / gcd 这两个数互质了，也就是 gcd( a / gcd ，b / gcd ) = 1，然后。。。
lcm = gcd * (a / gcd) * (b / gcd)
lcm = (a * b) / gcd
所以。。a*b = gcd * lcm
}
所以要求lcm，先求gcd
辣么，问题来了，gcd怎么求
辗转相除法
while循环
LL gcd(LL a, LL b){
LL t;
while(b){
t = b;
b = a % b;
a = t;
}
return a;
}
还有一个递归写法
LL gcd(LL a, LL b){
if(b == 0) return a;
else return gcd(b, a%b);
}
LL gcd(LL a, LL b){
return b ? gcd(b, a%b) : a;
}
//两种都可以
辣么，lcm = a * b / gcd
(注意，这样写法有可能会错，因为a * b可能因为太大 超出int 或者 超出 longlong)
所以推荐写成 ： lcm = a / gcd * b
然后几个公式自己证明一下
gcd(ka, kb) = k * gcd(a, b)
lcm(ka, kb) = k * lcm(a, b)
上次做题碰到这个公式
lcm(S/a, S/b) = S/gcd(a, b)
S = 9，a = 4，b = 6，小数不会lcm，只好保留分数形式去通分约分。
当我看到右边那个公式。。。。
(╯°Д°)╯┻━┻
这TM我怎么想的到，给我证明倒是会证。 T_T
【附录】
这里给出使用欧几里得算法求最大公约数的递归和非递归的程序，同时给出穷举法求最大公约数的程序。
从计算时间上看，递推法计算速度最快。
程序中包含条件编译语句用于统计分析计算复杂度。
/* * 计算两个数的最大公约数三种算法程序 */ #include <stdio.h> //#define DEBUG #ifdef DEBUG int c1=0, c2=0, c3=0; #endif int gcd1(int, int); int gcd2(int, int); int gcd3(int, int); int main(void) { int m=42, n=140; printf("gcd1: %d %d result=%d\n", m, n, gcd1(m, n)); printf("gcd2: %d %d result=%d\n", m, n, gcd2(m, n)); printf("gcd3: %d %d result=%d\n", m, n, gcd3(m, n)); #ifdef DEBUG printf("c1=%d c2=%d c3=%d\n", c1, c2, c3); #endif return 0; } /* 递归法：欧几里得算法，计算最大公约数 */ int gcd1(int m, int n) { #ifdef DEBUG c1++; #endif return (m==0)?n:gcd1(n%m, m); } /* 迭代法（递推法）：欧几里得算法，计算最大公约数 */ int gcd2(int m, int n) { while(m>0) { #ifdef DEBUG c2++; #endif int c = n % m; n = m; m = c; } return n; } /* 连续整数试探算法，计算最大公约数 */ int gcd3(int m, int n) { if(m>n) { int temp = m; m = n; n = temp; } int t = m; while(m%t || n%t) { #ifdef DEBUG c3++; #endif t--; } return t; }
关键代码（正解）：
/* 迭代法（递推法）：欧几里得算法，计算最大公约数 */
int gcd(int m, int n)
{
while(m>0)
{
int c = n % m;
n = m;
m = c;
}
return n;
}
数论——gcd&&lcm
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。