首页dut-fun-1 最大公约数与最小公倍数

dut-fun-1 最大公约数与最小公倍数

时间: 2025-03-07 08:18:01 浏览: 38

### 关于最大公约数与最小公倍数 #### 定义两个或多个整数共有约数中最大的一个称为这些整数的最大公约数 (Greatest Common Divisor, GCD)[^2]。对于任意两个正整数 \( a \) 和 \( b \)，如果存在一个正整数 \( d \)，使得 \( d|a \) 并且 \( d|b \)，那么 \( d \) 是 \( a \) 和 \( b \) 的公约数。最小公倍数 (Least Common Multiple, LCM) 则是指能够同时被若干个给定的自然数整除的最小的那个自然数[^1]。具体来说，\( X \) 能够成为 \( a \) 和 \( b \) 的最小公倍数意味着 \( X \) 可以被 \( a \) 整除也可以被 \( b \) 整除，并且不存在更小的这样的 \( Y \) 同时满足上述条件。 #### 性质关系最大公约数和最小公倍数之间有着密切的关系：\[ \text{LCM}(a,b)\times\text{GCD}(a,b)=|ab|\] #### 算法实现为了计算最大公约数，常用的方法有辗转相减法、穷举试除法以及欧几里得算法（即辗转相除法）。其中最高效的是后者： ```cpp int gcd(int a,int b){ while(b!=0){ int temp=a%b; a=b; b=temp; } return abs(a); } ``` 而求解最小公倍数则可以通过先得到两者的乘积再除以其最大公约数来获得: ```cpp long long lcm(long long a,long long b){ return fabs((double)a/(double)b*gcd(a,b)); } // 或者直接利用上面提到过的性质简化为如下形式： // long long lcm(long long a, long long b){return abs(a*b)/gcd(a,b);} ``` 注意这里使用 `fabs` 函数是为了防止溢出情况的发生；另外当处理较大数值时建议采用64位数据类型存储结果以确保精度。

阅读全文