H - Least Common Multiple H - 最小公倍数

发布时间：2024年01月19日

题目

The least common multiple (LCM) of a set of positive integers is the smallest positive integer which is divisible by all the numbers in the set. For example, the LCM of 5, 7 and 15 is 105.
一组正整数的最小公倍数 （LCM） 是最小的正整数，可以被该集合中的所有数字整除。例如，5、7 和 15 的 LCM 为 105。
?

Input

Input will consist of multiple problem instances. The first line of the input will contain a single integer indicating the number of problem instances. Each instance will consist of a single line of the form m n1 n2 n3 ... nm where m is the number of integers in the set and n1 ... nm are the integers. All integers will be positive and lie within the range of a 32-bit integer.
输入将包含多个问题实例。输入的第一行将包含一个整数，指示问题实例的数量。每个实例将由一行组成，格式为 m n1 n2 n3 ...nm 其中 m 是集合中的整数数，n1 ...nm 是整数。所有整数都是正数，并且位于 32 位整数的范围内。

Output

For each problem instance, output a single line containing the corresponding LCM. All results will lie in the range of a 32-bit integer.
对于每个问题实例，输出包含相应 LCM 的单行。所有结果都将位于 32 位整数的范围内。

Sample

InputcopyOutputcopy
2
3 5 7 15
6 4 10296 936 1287 792 1

105

思路?

如果将所有数都算起来以大数为标准进行寻找，由于数据量的数量众多，同时数据范围很大，放一起进行查找的话很容易出现问题，和上题类似，我们可以采用逐个计算的方法，来减少时间复杂度，具体的代码如以下实现。

代码实现

#include <bits/stdc++.h>
using namespace std;
int lcm(int a,int b){
	return a/__gcd(a,b)*b;//计算最小公倍数
}
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);//关闭同步流
	int t;
	cin>>t;
	while(t--){//多实例
		int m,n=1,e;
		cin>>m;//个数
		while(m--){
			cin>>e;
			n=lcm(e,n);//逐个计算，减少时间复杂度
		}
		cout<<n<<endl;//输出
	}
	return 0;
}

总结

本题延续了上题的分开计算，根据输入逐个计算，从而减少一起计算的麻烦和时间复杂度，希望大家能够理解和认识到这种思想，在时间超限的情况下通过该种方法进行简化和实现。

尾声

分立的计算能够把整体的计算化为简单的各部分，从而简化题目的要求与实现，如果觉得作者写的还不错的话，记得留下你的点赞收藏和关注哦~

文章来源:https://blog.csdn.net/2302_79862641/article/details/135700762
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
最新文章