第二次周赛F题（HDU-1019）

ゝ一纸荒年。 2024-02-19 15:01 6阅读 0赞

问题链接：[https://vjudge.net/problem/HDU-1019][https_vjudge.net_problem_HDU-1019]

问题简述：第一行输入n，接下来有n个测试实例，每一个测试实例先输入一个数字，代表接下来要输入几个数字，求这几个数字的最小公倍数。（不包括每一个测试实例的第一个数字）

Get：两个数的最小公倍数等于（这两个数的积）/（这两个数的最大公约数）。

用辗转相除法计算(也可以用更相减损术)：

第一种方法：递归  
AC代码：

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

这一行`gcd（）`中`b`和`a[i][j]`的位置可以互换，没有影响

cnt = b / gcd(b, a[i][j])*a[i][j];

第二种方法：迭代法  
AC代码：

#include <iostream>
    using namespace std;
    int main()
    {
        
    	long long a[100][100], b, cnt,s;
    	int n,i,j;
    	cin >> n;
    	for (i = 0; i < n; i++)
    	{
        
    		cin >> a[i][0];
    		b = cnt = 1;
    		for (j = 1; j < a[i][0]+1; j++)
    		{
        
    			cin >> a[i][j];
    			s = a[i][j] * b;
    			while (b)
    			{
        
    				int temp = a[i][j] % b;//因为b的初始值是1，所以第一次循环不用比较a[i][j]和b的大小；后面输入的a[i][j]如果比b（即最小公倍数）小，也不用比较大小，因为下面两步交换了它们的值.
    				a[i][j] = b;
    				b = temp;
    			}
    			cnt = s/a[i][j];
    			b = cnt;
    		}
    		cout << cnt << endl;
    	}
    }

相关链接：[https://blog.csdn.net/qq\_41572774/article/details/82500428][https_blog.csdn.net_qq_41572774_article_details_82500428]  
[https://blog.csdn.net/yopilipala/article/details/65934939][https_blog.csdn.net_yopilipala_article_details_65934939]

[https_vjudge.net_problem_HDU-1019]: https://vjudge.net/problem/HDU-1019
[https_blog.csdn.net_qq_41572774_article_details_82500428]: https://blog.csdn.net/qq_41572774/article/details/82500428
[https_blog.csdn.net_yopilipala_article_details_65934939]: https://blog.csdn.net/yopilipala/article/details/65934939