S - Lowest Common Multiple Plus 求n个数的最小公倍数

曾经终败给现在 2022-12-23 09:45 187阅读 0赞

### 求n个数的最小公倍数 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUxNjMxNjM5_size_16_color_FFFFFF_t_70_pic_center]  
！！注意！！

1.要知道一个公式：**x\*y=最小公倍数（lcm）\*最大公因数（gcd）** 那么这里可以用这个公式得出 **lcm=x/最大公因数（gcd）\*y**

2.自己编写**gcd函数**  
（其实本来有\_\_gcd()函数的，但不知道为啥过不了）  
gcd函数代码如下，返回最大公因数：

long long gcd(long long b,long long c)
    {
        
    	if(c==0) return b;
    	else return gcd(c,b%c);
    }

3.求最小公倍数，代码如下：

for(i=1;i<n;i++)
    {
        
    	b=b/gcd(b,a[i])*a[i];
    }

一开始是要设置 **b=a\[0\]** 的

这里其实有**递归**的思想，就是第一次先求开头两个数的最小公倍数，再用这个求出的最小公倍数去和第三个数求最小公倍数。如此循环往复。

完整代码如下：

#include <iostream>
    #include <algorithm>
    using namespace std;
    long long gcd(long long b,long long c)
    {
        
    	if(c==0) return b;
    	else return gcd(c,b%c);
    }
    int main()
    {
        
    	long long b,i,n;
    	long long a[1001];
    	while(cin>>n)
    	{
        
    		for(i=0;i<n;i++)
    		{
        
    			cin>>a[i];
    		}
    		b=a[0];
    		if(n==1) 
    		{
        
    			cout<<b;
    			continue;
    		}
    		for(i=1;i<n;i++)
    		{
        
    			b=b/gcd(b,a[i])*a[i];
    		}
    		cout<<b<<endl;
    	}
    	
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUxNjMxNjM5_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/9a60a7c1a4f642159a9615cf52d935ac.png